Jump to content
Sign in to follow this  
AprendizZ

Problema com automato finito.

Recommended Posts

AprendizZ

Caros amigos,

Estou a precisar de uma ajuda com um problema relacionado com automatos finitos.

Preciso de criar automato finito que:

- lê cadeias de binárias (ex.: 0, 1, 10, 10110, 10001010, etc., mas não são aceite cadeias começadas por 0 excepto o 0 unitário;

- essas cadeias têm de ser a conversão de números decimais divisíveis por 6 (ex.: 0, 110, 1100, 10010,etc.);

- as cadeias não podem conter a cadeia 101;

mas até ao momento ainda não consegui resolver este automato.

Eis uma lista:

(cadeias aceites)
0
110
1100
10010
11000
11110
100100
110000
111100
1000100
1100010
(cadeias rejeitadas)
10
100
1000
10000
100000
101
1010
0101
10101
1011
111010
11010
 

E até ao momento já consegui fazer o seguinte automato:

http://dl.dropbox.com/u/7275324/LFA1112_P1.png

Todas as cadeias aceites são admitidas, nas cadeias rejeitadas as duas últimas também são aceites quando deveriam ser rejeitadas. Uma ajudinha. Obrigado.

Share this post


Link to post
Share on other sites
KTachyon

Entre os estados q5 e q6 estás a permitir que a sub-cadeia 101 seja validada (o que não queres que aconteça, segundo a tua terceira regra). No mínimo dos mínimos tens que obrigar que passe por dois zeros antes de chegar ao estado em que possa voltar a apanhar um 1. Deves precisar de mais um estado final.

E repara que o autómato valida o 14 (1110), que não é divisível por 6.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
KTachyon

Bem... pensar na forma de representação disto pode ser complicado, mas há algumas considerações que tens que ter:

1. Tens que pensar em binário

2. Pode ser mais fácil desenvolveres a maquina de estados se pensares nas propriedades dos números que compõem o valor 6 (ou seja, o 2 e o 3).

A propriedade que distingue o número 2 (10), é que todos os números binários terminados em 10 são divisíveis por 2. Ou seja, em binário, qualquer combinação de dígitos terminada com 0 é divisível por 2. E este será sempre o valor inserido no teu último estado, o que está correcto no teu autómato.

O teu problema é arranjar a representação da divisão por 3. Uma das propriedades é que (n1 - n2) % 3 == 0, sendo n1 o número de 1 em posições pares da cadeia, e o n2 o número de 1 em posições ímpar. O DFA simplificado seria qualquer coisa como:

Q0: 0 -> Q0, 1 -> Q1, estado final

Q1: 1 -> Q0, 0-> Q2

Q2: 1 -> Q2, 0 -> Q1

(mais informações em: http://www.idt.mdh.se/kurser/cd5560/02_03/senaste_nytt/ralfs_divby3.pdf)

Ou seja, tens que aplicar o estado da divisão por 2, para obrigar a que o número seja divisível por 6, logo alteras o teu estado final para obrigar a que haja sempre um zero no final da cadeia:

Q0: 0 -> Q3, 1 -> Q1 (o 0 é obrigatório passa para um novo estado)

Q1: 1 -> Q0, 0-> Q2

Q2: 1 -> Q2, 0 -> Q1

Q3: 0 -> Q3, 1 -> Q1, estado final (um 1 tem o mesmo trajecto que teria com Q0)

Agora, se queres permitir apenas um único zero inicial, tens que voltar a alterar o estado Q0 (criar um novo estado final) e criar um novo que lide com os retornos de Q1:

Q0: 0 -> Q4, 1 -> Q1

Q1: 1 -> Q5, 0 -> Q2

Q2: 1 -> Q2, 0 -> Q1

Q3: 0 -> Q3, 1 -> Q1, estado final

Q4: estado final

Q5: 1 -> Q1, 0 -> Q3

Finalmente, falta apenas remover a possibilidade de existirem cadeias '101'. Essa possibilidade pode acontecer nas passagens Q1->Q5->Q3->Q1 e Q0->Q1->Q2->Q2.

Como tens o Q3  a repetir zeros, não estragas o autómato se adicionares um estado entre o Q5 e o Q3 que obrigue a colocação de mais um zero, mas tens que ter em consideração que como Q3 é estado final, este novo estado intermédio também tem que ser estado final (caso contrário não validas o 110).

O problema estaria na tua passagem para o Q2 que logo de seguida poderia repetir 1s. Não podes colocar um novo estado para obrigares à entrada de um novo zero, porque irias destruir a validação da divisibilidade por 3, mas podes simplesmente remover a repetição de 1s.

Se não me tiver enganado no raciocínio, no final terás qualquer coisa como:

Q0: 0 -> Q4, 1 -> Q1

Q1: 1 -> Q5, 0 -> Q2

Q2: 0 -> Q1

Q3: 0 -> Q3, 1 -> Q1, estado final

Q4: estado final

Q5: 1 -> Q1, 0 -> Q3

Q6: 0 -> Q3, estado final


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
AprendizZ

http://dl.dropbox.com/u/7275324/LFA1112_P1b.png

KTachyon, este é o resultado da tua ajuda. Entretanto tive que fazer pequenas correcções:

Q5: 1 -> Q1, 0 -> Q6

Q6: 0 -> Q3, estado final

(acho que era isto que querias dizer, senão o estado Q6 era simplesmente um estado final

só com uma saída 0 e sem qualquer entrada).

Mas após fazer testes exaustivos continua a verificar-se que ainda não está à prova de "bala".

O valor binário 1000100010 deveria ser aceite e não é (é divisível por 6 e não tem cadeia 101).

Ainda falta alguma coisita, mas não consigo detectar onde.

Share this post


Link to post
Share on other sites
Warrior

Uma propriedade que talvez vos esteja a falhar:

Qualquer estado ao qual seja possível chegar vindo de um estado final (em que a cadeia seja aceite) utilizando um 0, tem que ser final também, uma vez que é uma multiplicação por 2 e portanto o resultado continua a ser múltiplo de 6. Ou seja, tem que existir um ciclo de 0s no diagrama.

Share this post


Link to post
Share on other sites
KTachyon

KTachyon, este é o resultado da tua ajuda. Entretanto tive que fazer pequenas correcções:

Q5: 1 -> Q1, 0 -> Q6

Q6: 0 -> Q3, estado final

(acho que era isto que querias dizer, senão o estado Q6 era simplesmente um estado final

só com uma saída 0 e sem qualquer entrada).

Mas após fazer testes exaustivos continua a verificar-se que ainda não está à prova de "bala".

O valor binário 1000100010 deveria ser aceite e não é (é divisível por 6 e não tem cadeia 101).

Ainda falta alguma coisita, mas não consigo detectar onde.

Era isso. E o problema que colocaste tem lógica. Quando disse que bastava remover a repetição de 1s no estado Q2, estava errado. Dessa forma não possibilitamos a entrada de 1s após um número ímpar de zeros superior a 1. As entradas em posições pares já estão correctas.

Basicamente, a partir do Q2 serão precisos mais nós para garantir a entrada de 1s:

Q2: 0 -> Q7 (deixa de retornar para Q1, o duplo zero passa a ser tratado pelo Q7)

Q7: 0 -> Q8, 1 -> Q5

Q8: 1 -> Q9, 0 -> Q1

Q9: 1 -> Q9, 0 -> Q10

Q10: 0 -> Q2

Assim penso que já eliminas a possibilidade de validar 101 sem afectar a divisibilidade por 3 (e, consequentemente, por 6). Com números pares de zero, o 1 tem que passar para o Q5, enquanto que se o número for ímpar, o 1 tem que passar pelo Q9.

Penso que o raciocínio já deve estar correcto, mas, de qualquer forma, estou a fazer isto de cabeça, é normal que me escape alguma coisa ;)

EDIT: Aparentemente funciona :D

Válidos:

  0. 0
  6. 110
12. 1100
18. 10010
24. 11000
30. 11110
36. 100100
48. 110000
60. 111100
66. 1000010
72. 1001000
78. 1001110
96. 1100000
102. 1100110
114. 1110010
120. 1111000
126. 1111110
132. 10000100
144. 10010000
156. 10011100
192. 11000000
198. 11000110
204. 11001100
228. 11100100
240. 11110000
252. 11111100
258. 100000010
264. 100001000
270. 100001110
288. 100100000
294. 100100110
306. 100110010
312. 100111000
318. 100111110
384. 110000000
390. 110000110
396. 110001100
402. 110010010
408. 110011000
414. 110011110
450. 111000010
456. 111001000
462. 111001110
480. 111100000
486. 111100110
498. 111110010
504. 111111000
510. 111111110
516. 1000000100
528. 1000010000
540. 1000011100
546. 1000100010
576. 1001000000
582. 1001000110
588. 1001001100
612. 1001100100
624. 1001110000
636. 1001111100
768. 1100000000
774. 1100000110
780. 1100001100
786. 1100010010
792. 1100011000
798. 1100011110
804. 1100100100
816. 1100110000
828. 1100111100
900. 1110000100
912. 1110010000
924. 1110011100
960. 1111000000
966. 1111000110
972. 1111001100
996. 1111100100

Não válidos:

 42. 101010
54. 110110
84. 1010100
90. 1011010
108. 1101100
138. 10001010
150. 10010110
162. 10100010
168. 10101000
174. 10101110
180. 10110100
186. 10111010
210. 11010010
216. 11011000
222. 11011110
234. 11101010
246. 11110110
276. 100010100
282. 100011010
300. 100101100
324. 101000100
330. 101001010
336. 101010000
342. 101010110
348. 101011100
354. 101100010
360. 101101000
366. 101101110
372. 101110100
378. 101111010
420. 110100100
426. 110101010
432. 110110000
438. 110110110
444. 110111100
468. 111010100
474. 111011010
492. 111101100
522. 1000001010
534. 1000010110
552. 1000101000
558. 1000101110
564. 1000110100
570. 1000111010
594. 1001010010
600. 1001011000
606. 1001011110
618. 1001101010
630. 1001110110
642. 1010000010
648. 1010001000
654. 1010001110
660. 1010010100
666. 1010011010
672. 1010100000
678. 1010100110
684. 1010101100
690. 1010110010
696. 1010111000
702. 1010111110
708. 1011000100
714. 1011001010
720. 1011010000
726. 1011010110
732. 1011011100
738. 1011100010
744. 1011101000
750. 1011101110
756. 1011110100
762. 1011111010
810. 1100101010
822. 1100110110
834. 1101000010
840. 1101001000
846. 1101001110
852. 1101010100
858. 1101011010
864. 1101100000
870. 1101100110
876. 1101101100
882. 1101110010
888. 1101111000
894. 1101111110
906. 1110001010
918. 1110010110
930. 1110100010
936. 1110101000
942. 1110101110
948. 1110110100
954. 1110111010
978. 1111010010
984. 1111011000
990. 1111011110

Uma propriedade que talvez vos esteja a falhar:

Qualquer estado ao qual seja possível chegar vindo de um estado final (em que a cadeia seja aceite) utilizando um 0, tem que ser final também, uma vez que é uma multiplicação por 2 e portanto o resultado continua a ser múltiplo de 6. Ou seja, tem que existir um ciclo de 0s no diagrama.

O problema não era a multiplicidade por 2, mas a multiplicidade por 3. A multiplicidade por 2 só obriga à existência de um zero no final da cadeia. A multiplicidade por 3 é que obriga a uma validação um pouco mais complexa. Independentemente do posicionamento dos zeros na cadeia, o número só e divisível por 3 se depois do estado Q5 só forem inseridos zeros. Qualquer 1 inserido implica que tenha que haver novo acerto de 1s para que a cadeia volte a ser divisível por 3.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
AprendizZ

KTachyon, com base nas tuas indicações este é o produto final em diagrama:

http://dl.dropbox.com/u/7275324/LFA1.png

mas nos meus testes continuam a ser aceites valores com cadeias 101 (que deviam ser rejeitados).

Por exemplo:

101010

1010100

1011010

10100010

10101000

10101110

entre outros.

Talvez tenha-me passado algum passo que tenhas indicado e que eu não percebi.  ;)

Share this post


Link to post
Share on other sites
KTachyon

Puseste a repetição do 1 no estado Q2 a mais.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
AprendizZ

Era isso mesmo, já me tinha esquecido que era para retirar.

Agora já está certo.

Entretanto tentei encontrar uma solução mais simplificada (pensar em binário como disseste):

http://dl.dropbox.com/u/7275324/LFA2.png

mas não me está a resultar nos valores mais altos (11000110, 110001100, 1000100010, 1001000110, 1100000110, são alguns). Deve ser alguma coisa relacionada com o número ímpar de 0s.

Share this post


Link to post
Share on other sites
KTachyon

Sim, tem o mesmo problema nos estados q4 e q6. Mas repara que esse autómato já não é deterministico. A partir do estado q2, podes receber um zero e ir para q6 ou para q3.

E tem o mesmo problema que o anterior antes de adicionarmos os últimos 4 estados. Basicamente, para essa solução funcionar tinhas que adicionar 4 novos estados para o q4 e 4 novos estados para o q6, e acabavas por ficar com 15 estados em vez de 11 :cheesygrin:


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
AprendizZ

Ok, percebi... às vezes quanto mais se quer simplificar, mais se complica.

Fica aqui o meu muito obrigado por toda a ajuda dada, na percepção deste problema.

Obrigado.

Share this post


Link to post
Share on other sites
AprendizZ

Já agora deixo aqui dicas para a solução deste problema:

1. Fazer o autómato (A1) que determina a divisibilidade por 6 (a mais simples que consegui foi a que o KTachyon me ajudou a fazer);

2. Fazer o autómato (A2) que aceite cadeias de binários que contenham a cadeia 101;

3. Concluir fazendo a "diferença de autómatos", A1 - A2, ou seja, na reunião dos dois eliminar os estados que não fazem falta e só assumir os estados finais que existem em A1.

Espero ter ajudado a quem esteja interessado.  :thumbsup:

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.