Linguagens Formais e Autômatos

1)  Para a cadeia ser aceita ela precisa ser da forma “x01y”, onde x e y são quaisquer strings de “0’s” e “1’s”. O autômato inicia no estado qo, e ao receber como entrada “0” ou “1” ele vai ao estado q1, garantindo assim que a cadeia tenha uma string x, no estado q1 ele vai começar a “procurar” o “0”, então caso receba como entrada “0” vai para próximo estado q2 e caso receba o 1 permanece em q1 “procurado” o “0”, em q2 vai acontecer algo parecido com o que acontece com q1, porém agora estaremos procurando o “1”, caso encontre seguimos para q3 e caso receba como entrada “0” permaneceremos em q2, chegando em q3 garantimos que a cadeia de entrada possui a string “01”, sendo assim precisamos apenas de mais alguma entrada, sendo “0” ou “1” para ele ir ao estado de aceitação q4, garantindo que a cadeia inserida também possui um y.

[pic 1]

2) Para a cadeia ser aceita ela deve possuir um número par de “0’s”. Nesse autômato, somente o número de “0’s” importa, portanto as entradas de “1” não farão mudanças de estados. Em q0, o estado inicial, ao lermos “0” iremos ao q1, q1 será um estado onde possuímos um número ímpar de “0’s”, e em q1 ao lermos q0 iremos a q2, o estado de aceitação e o estado onde possuímos um número par de “0’s”, ao ler 0 em q2 retornamos a q1, pois o número de 0 será ímpar.

[pic 2]

3) NÃO FIZ

4) Para a cadeia ser aceita neste autômato ela deve terminar em 00. Iniciamos em q0, o estado inicial, e ficamos nele até ter uma entrada de “0”, ao ler “0” iremos para q1, em q1 ao ler o “0” iremos para q2, o estado de aceitação, e caso ler “1” voltamos para q0, em q2 caso a entrada seja “0” ficamos nele e caso a entrada seja “1” voltamos ao início.

q0 representa que 0 “0” foram lidos em sequência

q1 representa que lemos 1 “0”

e q2 representa que lemos 2 ou mais “0’s”

[pic 3]

5)  Para essa cadeia ser aceita ela deve possuir três 0’s consecutivos.

Iniciamos em q0, estado inicial, onde nenhum 0 foi lido ainda, caso entrada seja “0” vamos para q1 e caso seja “1” permanece em q0.

Em q1, onde já foi lido um “0”, caso a entrada seja “0” vamos para q2 e caso a entrada seja “1” retornamos para q0.

Em q2, onde já foi lido dois “0”, caso a entrada seja “0” vamos para q3 e caso a entrada seja “1” retornamos para q0.

q3 é o estado de aceitação, e independente da entrada permaneceremos em q3, uma vez que já foi identificado três 000 na cadeia inserida.

[pic 4]

6) Para a cadeia ser aceita nesse automato ela precisa conter a substring 011.

Começamos em q0, o estado inicial, nele procuraremos o “0”, caso entrada seja 0 vamos para q1 e caso seja “1” permaneceremos em q0.

Em q1, procuraremos o “1”, caso a entrada seja “1” vamos para q2 e caso seja “0” permaneceremos em q1.

Em q2, procuraremos o “1”, caso a entrada seja “1” vamos para q3 e caso seja “0” voltaremos para q1.