Esta máquina de estado finito (FSM) aceita números binários que são divisíveis por três. Em teoria, os estados devem ser iguais ao valor n mod 3, mas como isso funciona para números binários. O que eu não consigo é como as transições se juntam porque uma nova entrada 0 ou 1 não significa que um número fixo seja adicionado ao total N. Você pode por favor me ajudar a entender que Obrigado antecipadamente Os estados A, B e C correspondem a entradas congruentes a 0,1 e 2 mod 3, respectivamente. Suponha que a entrada até agora representa um múltiplo de 3, de modo que você esteja no estado A. A 0 multiplica o número atual por 2, então ainda é um múltiplo de 3 e você ainda está no estado A. A 1 multiplica por 2 e Adiciona 1, tornando-se congruente a 1 mod 3 e colocando você no estado B. Se o número atual é congruente a 1 mod 3, você está no estado B. Uma entrada de 0 dobra o número, tornando-se congruente a 2 mod 3 e tendo Você deve indicar C. Uma entrada de 1, por outro lado, duplica o número, tornando-se congruente com 2 mod 3 e, em seguida, adiciona 1, tornando-se um múltiplo de 3 e enviando você para o estado A. Da mesma maneira que você Pode analisar o que acontece quando o número atual é congruente a 2 mod 3 e você está no estado C: duplicar o número torna congruente a 4 e, portanto, a 1 mod 3 e move-lo para o estado B, e dobrando-o e adicionando um deixa-lo em Estado C. Assim, os três estados realmente estão conectados corretamente. Tudo isso se resume ao que vejo Ted ter dado em sua resposta: quando você lê um pouco b, você está mudando o número atual um lugar para a esquerda, o que multiplica por 2, e então você está adicionando b o FSM imita o efeito Daquela operação sobre o resíduo do número mod 3. Respondida May 3 12 at 7:14 Aqui está outra abordagem, mais pedante: Deixe o número n soma dk 2k. Defina rk 2k bmod 3 e observe que rk2 quando k é estranho e rk 1 quando k é igual. Assim, n bmod 3 soma dk rk bmod 3. Esta é a chave para criar um diagrama de estado, com os dígitos binários d0. D como entradas. Para calcular a soma, é preciso rastrear a soma existente (módulo 3, é claro) e se o índice é ímpar ou mesmo (para saber o valor de rk). Portanto, o espaço dos estados é o tempo. É direto criar o diagrama de estado com estados aceitos (0, impar) e (0, mesmo). (0, ímpar) amp (0, ímpar) amp (0, ímpar) amplificador (0, ímpar) amp (0, ímpar) (1, par) amp (2, par) (1, par) amp (1, impar) amp (0, impar) (2, impar) amp (2, even) amp (0, even) (2, even) Amp (2, impar) amp (1, impar) end O catch é que existem 6 estados, não 3 como no diagrama acima. No entanto, se aplicarmos o algoritmo de preenchimento de tabela FSM (por exemplo, ver Hopcroft, Motwani, Ullman, Introdução à Teoria de Autômatos, Línguas e Computação) para encontrar estados indistinguíveis, achamos que os seguintes pares são indistinguíveis:. O FSM resultante é idêntico ao FSM acima, com a identificação de estado A sim, B sim e C sim. Respondeu May 3 12 at 20:06 Isn39t este o oposto rk1 quando k é mesmo. E rk 2 quando k é ímpar. (Por exemplo, k1: rk (21 mod 3) 2 enquanto k2: rk (22 mod 3) 1) ndash Dor Sep 25 15 at 17:32 Dor: Obrigado por apanhar esse ndash copper. hat Sep 25 15 at 17:50 Sua resposta 2017 Stack Exchange, IncIm trabalhando em um conjunto de problemas para uma classe, e pensei em uma pergunta relacionada com o que eu estava trabalhando. Existe um número mínimo de estados que um autômato finito deve ter para aceitar cadeias binárias que representam números divisíveis por um inteiro n Em um conjunto de problemas anteriores, eu era capaz de construir um DFA que aceitou cadeias binárias divisíveis por 3 com 3 estados . Isso é uma coincidência, ou há algo inerente ao problema geral de detectar cordas divisíveis por n que sugiram um número mínimo de estados que eu prometo que isso não responderá a uma questão de lição de casa para mim. ) Perguntou Jan 29 12 em 0:35 HuckBennett Eu concordo com Kaveh que esta pergunta deve ser fechada em cstheory, na maior parte para ser consistente. No entanto, eu também concordo com você: esta é uma pergunta divertida e quando você vê pela primeira vez DFAs é definitivamente um você deveria estar se perguntando. Eu acho que o OP deve tentar se divertir trabalhando a resposta por si mesmo e, em seguida, consulte math. SE para obter mais informações. Ndash Artem Kaznatcheev 9830 Jan 29 12 às 6:10 Esta lição de casa isn39t (embora seja inspirado por uma questão de casa), it39s uma questão interessante, eu don39t acreditar que é um resultado bem conhecido ea resposta à pergunta apareceu em um jornal de pesquisa. Eu não vejo por que ele deve ser fechado. O limite superior era lição de casa, e é de fato fácil, mas a questão era sobre o limite inferior. Ndash Peter Shor Jan 29 12 às 13: 43 Eu auto-estudo de expressões regulares e encontrei um interessante problema de prática on-line que envolve escrever uma expressão regular para reconhecer todos os números binários divisíveis por 3 (e apenas esses números). Para ser honesto, o problema pediu para construir um DFA para tal cenário, mas eu pensei que deveria ser equivalentemente possível usando expressões regulares. Eu sei que há uma pequena regra no lugar para descobrir se um número binário é divisível por 3: tomar o número de uns em lugares parados no dígito e subtrair pelo número de uns em lugares ímpares no dígito - se este for igual a zero , O número é divisível por 3 (exemplo: 110 - 1 no slot 2 pares e 1 na ranhura 1 ímpar). No entanto, estou tendo alguns problemas para adaptar isto a uma expressão regular. O mais próximo Ive vir é perceber que o número pode ser 0, de modo que seria o primeiro estado. Eu também vi que todos os números binários divisíveis por 3 começam com 1, de modo que seria o segundo estado, mas Im preso a partir daí. Alguém poderia ajudar out perguntou Mar 11 13 às 1:50 Seguindo o que Oli Charlesworth diz, você pode construir DFA para divisibilidade de base b número por um certo divisor d. Onde os estados no DFA representam o restante da divisão. Para o seu caso (base 2 - número binário, divisor d 3 10): Note que o DFA acima aceita cadeia vazia como um número divisível por 3. Isso pode ser facilmente corrigido adicionando um estado intermediário mais à frente: Conversão para a expressão regular teórica Pode ser feito com o processo normal. Conversão para regex prática em sabores que suporta regex recursiva pode ser feito facilmente, quando você tem o DFA. Isto é mostrado para o caso de (base b 10, d 7 10) nesta pergunta de CodeGolf. SE. Quebrando-o para baixo, você pode ver como ele é construído. O agrupamento atômico (ou não-backtracking grupo, ou um grupo que se comporta possessivamente) é usado para certificar-se apenas o vazio corda alternativo é correspondido. Este é um truque para emular (DEFINE) em Perl. Então, os grupos A a G correspondem ao restante de 0 a 6 quando o número é dividido por 7. Respondeu 11 de março às 6:44 Eu tenho outra maneira de resolver esse problema e acho que isso é mais fácil de entender. Quando dividimos um número por 3, podemos ter três remanescentes: 0,1,2. Podemos descrever um número que é divisível por 3 usando a expressão 3t (t é um número natural). Quando adicionamos 0 após um número binário cujo restante é 0, o número decimal real será duplicado. Porque cada dígito está se movendo para uma posição mais alta. 3t 2 6t, isso também é divisível por 3. Quando estamos adicionando um 1 após um número binário cujo restante é 0, o número decimal real será dobrado mais 1. Como cada dígito está se movendo para uma posição mais alta, seguido de um 1 3t 2 1. o restante é 1. Quando estamos adicionando um 1 após um número binário cujo restante é 1. O número decimal real será dobrado mais um, eo restante é 0 (3t 1) 2 1 6t 3 isto é divisível por 3. Quando estamos adicionando um 0 após um número binário cujo restante é 1. O número decimal real será dobrado. E o restante será 2 (3t 1) 2 6t 2. Quando estamos adicionando um 0 após um número binário cujo O restante é 2. O restante será 1. (3t 2) 2 3t 4 3 (2t 1) 1 Quando adicionamos um 1 após um número binário cujo restante é 2. Então o restante será 2. (3t 2) 2 1 t 5 3 (2t 1) 2. Não importa quantos 1 você adiciona a um número binário cujo restante é 2, o restante será 2 para sempre. (3 (t 1) 2) 2 1 3 (t 2) 5 3 (t 3) 2 respondido Nov 6 15 em 20:45 Os números binários divisíveis por 3 caem em 3 categorias: Números com dois consecutivos 1s ou dois 1s separados por Um número par de 0s. Efetivamente cada par se anula. (Ex 11, 110, 1100, 1001, 10010, 1111) (decimal: 3, 6, 12, 9, 18, 15) Números com três 1s cada um separados por um número ímpar de 0s. Esses trigêmeos também se cancelam. (Ex: 10101, 101010, 1010001, 1000101) (decimal: 21, 42, 81, 69) Alguma combinação das duas primeiras regras (incluindo uma dentro da outra) (por exemplo, 1010111, 1110101, 1011100110001) , 5937) Assim, uma expressão regular que leva em conta essas três regras é simplesmente: significa que o grupo de números anterior é opcional indica uma escolha de opções em cada lado dentro dos parêntesesBelow, eu escrevi uma resposta para n é igual a 5, mas você pode aplicar Mesma abordagem para desenhar DFAs para qualquer valor de n e qualquer sistema de número de posição, por exemplo binário, ternário. Primeiro, incline o termo Completar o DFA, um DFA definido no domínio completo em: Q Q é chamado de DFA Completo. Em outras palavras, podemos dizer que no diagrama de transição do DFA completo não há nenhuma borda ausente (por exemplo, de cada estado em Q há uma borda de saída presente para cada símbolo de linguagem). Nota: Algum tempo nós definimos DFA parcial como Q Q (Leia: Como faz: Q Q lê na definição de um DFA). Design DFA aceitando números binários divisíveis por número n: Etapa-1. Quando você divide um número por n, o lembrete pode ser 0, 1. (n - 2) ou (n - 1). Se restante é 0, esse meio é divisível por n caso contrário não. Então, no meu DFA haverá um estado q r que corresponderia a um valor restante r. Onde 0 lt r lt (n - 1). Eo número total de estados no DFA é n. Depois de processar uma string numérica, o estado final é q r implica que n r (operador de lembrete). Em qualquer autômato, o propósito de um estado é como elemento de memória. Um estado em um atomata armazena algumas informações como os fãs de comutação que podem dizer se o ventilador está em off ou no estado. Para n 5, cinco estados em DFA correspondendo a cinco informações de lembrete como se segue: Estado q 0 atingido se o lembrete é 0. Estado q 0 é o estado final (estado de aceitação). É também um estado inicial. Estado q 1 atinge se lembrete é 1, um estado não-final. Estado q 2 se lembrete é 2, um estado não-final. Estado q 3 se lembrete é 3, um estado não-final. Estado q 4 se lembrete é 4, um estado não-final. Usando a informação acima, podemos começar a desenhar o diagrama de transição TD de cinco estados da seguinte maneira: Então, 5 estados para 5 valores restantes. Depois de processar uma seqüência se o estado final se torna q 0, isso significa que o equivalente decimal da string de entrada é divisível por 5. Na figura q acima, o estado final marcado como dois círculos concêntricos. Além disso, eu tenho definido uma regra de transição: (q 0. 0) q 0 como um auto-loop para o símbolo 0 no estado q 0. Isso porque o equivalente decimal de qualquer string consistem apenas em 0 é 0 e 0 é divisível por n. Passo 2 . TD acima está incompleto e só pode processar seqüências de 0 s. Agora adicione algumas bordas mais para que ele possa processar seqüências de caracteres de números subseqüentes. Verifique a tabela abaixo, mostra novas regras de transição que podem ser adicionadas próxima etapa: Para processar a seqüência binária 1 deve haver uma regra de transição: (q 0.1) q 1 Dois: - a representação binária é 10. o estado final deve ser q 2 . E para processar 10. precisamos apenas adicionar mais uma regra de transição: (q 1. 0) q 2 Caminho. (Q 0) 1 (q 1) 0 (q 2) Três: - em binário é 11. estado final é q 3. E precisamos adicionar uma regra de transição: (q.1.1) q 3 Caminho. (Q 0) 1 (q 1) 1 (q 3) Quatro: - em binário 100. estado final é q 4. TD já processa a cadeia de prefixos 10 e só precisamos adicionar uma nova regra de transição: (q 2. 0) q 4 Path. (Q 0) 1 (q 1) 0 (q 2) 0 (q 4) Passo 3. Cinco 101 Acima diagrama de transição na figura-2 ainda está incompleta e há muitas arestas ausentes, para um exemplo nenhuma transição é definida para: (q 2 .1) -. E a regra deve estar presente para processar strings como 101. Como 101 5 é divisível por 5, e para aceitar 101 eu vou adicionar: (q 2 .1) q 0 na figura acima-2. Caminho: (q 0) 1 (q 1) 0 (q 2) 1 (q 0) com esta nova regra, o diagrama de transição torna-se da seguinte forma: Abaixo em cada passo, TD como um DFA completo. Podemos processar 11 no TD presente na figura 3 como: (q 0) 11 (q 3) 0 (). Porque 6 5 1 isto significa adicionar uma regra: (q 3, 0) q 1. Passo-6 Adicionar Doze, Treze, Quatorze Número total de arestas no diagrama de transição a figura-12 é 15 Q 5 3 (um DFA completo). E este DFA pode aceitar todas as seqüências consistem sobre aqueles decimais equivalente é divisível por 5. Se você notar em cada etapa, na tabela há três entradas porque em cada etapa eu adiciono todos os possíveis borda de saída de um estado para fazer um completo DFA (e Eu adiciono uma borda de modo qr estado obtém para resto é r) Para acrescentar ainda mais, lembre-se de união de duas linguagens regulares também são um regular. Se você precisar criar um DFA que aceite cadeias binárias, esses equivalentes decimais serão divididos por 3 ou 5, então desenhe dois DFAs separados para divisíveis por 3 e 5, então unam ambos os DFAs para construir o DFA alvo (para 1 lt n lt 10 seu Para unir 10 DFAs). Se você for convidado a desenhar o DFA que aceita cadeias binárias de tal forma que o decimal equivalente seja divisível por 5 e 3, então você está procurando o DFA de divisível por 15 (mas o que acontece com 6 e 8). Nota: Os DFAs desenhados com esta técnica serão minimizados DFA somente quando não há um fator comum entre o número n ea base, e. Não há entre 5 e 2 no primeiro exemplo, ou entre 5 e 3 no segundo exemplo, portanto, ambos os DFAs construídos acima são DFAs minimizados. Se você estiver interessado em ler mais sobre possíveis mini estados para o número n e base b ler papel: Divisibilidade e Complexidade do Estado. Abaixo eu adicionei um script Python, eu escrevi-lo para se divertir enquanto aprende Python biblioteca pygraphviz. Estou adicionando, espero que possa ser útil para alguém de alguma forma. Design DFA para seqüências de caracteres b de base b divisível por número n: Assim, podemos aplicar acima truque para desenhar DFA para reconhecer cadeias de números em qualquer base b aqueles que são divisíveis um dado número n. Nesse DFA, o número total de estados será n (para n restante) eo número de arestas deve ser igual a b n mdash completo DFA: b número de símbolos no idioma do DFA e n número de estados. Usando o trufo acima, abaixo escrevi um script Python para desenhar DFA para base e número de entrada. No script, a função dividedbyN preenche as regras de transição do DFAs em etapas de número de base. Em cada step-num, eu converto num nums nums string usando a função baseN (). Para evitar o processamento de cada seqüência de caracteres de número, eu usei um lookuptable temporal de estrutura de dados. Em cada etapa, o estado final para números nums string é avaliado e armazenado em lookuptable para usar na próxima etapa. Para o gráfico de transição do DFA, escrevi uma função drawtransitiongraph usando a biblioteca Pygraphviz (muito fácil de usar). Para usar este script, você precisa instalar o graphviz. Para adicionar bordas coloridas no diagrama de transição, eu ganho aleatoriamente códigos de cores para cada função getcolordict do símbolo. Da mesma forma, insira a base 4 e o número 7 para gerar - dfa aceitando número de caracteres na base 4, esses são divisíveis em 7 Btw, tente alterar o nome do arquivo para. png ou. jpeg.
No comments:
Post a Comment