2) Para I = { a, b } , desenhe os AFD’s que reconheçam as seguintes linguagens: (2.0) a) L [ ( a* b * ) ( (aa)* (bb)* ) ] b) L [ ( a*b...
a) L [ ( a* b * ) ( (aa)* (bb)* ) ]
b) L [ ( a*b ab* ) ]
c) Sequências que tenham o PREFIXO ab ou o SUFIXO ab (ou ambos).
ATENÇÃO: verificar que a sequência babbbaba não deve ser reconhecida pelo seu AFD.
d) Sequências em que o PREFIXO de COMPRIMENTO DOIS coincide com o SUFIXO de COMPRIMENTO DOIS.
Exemplo de sequências reconhecidas (com os prefixos e sufixos sublinhados):
aa, bbb, aabaa, abbbbbab, baababba,
e) Sequências em o número de ocorrências da subsequência ab seja igual ao número de ocorrências da
subsequência ba. Exemplo de sequências reconhecidas:
λ, aa, bbb, aba, bab, abbabba,
💡 1 Resposta
Ed 
Desculpe, mas não consigo desenhar os AFDs aqui. No entanto, posso explicar como construir os AFDs para as linguagens mencionadas: a) L [ (a* ∪ b*) ((aa)* ∪ (bb)*) ] Para construir o AFD para essa linguagem, você precisa considerar os seguintes estados: - Estado inicial: q0 - Estado final: qf - Transições: - De q0 para si mesmo com a leitura de 'a' ou 'b' - De q0 para qf com a leitura de 'a' ou 'b' - De qf para si mesmo com a leitura de 'a' ou 'b' b) L [ (a*b ∪ ab*) ] Para construir o AFD para essa linguagem, você precisa considerar os seguintes estados: - Estado inicial: q0 - Estado final: qf - Transições: - De q0 para si mesmo com a leitura de 'a' - De q0 para qf com a leitura de 'b' - De qf para si mesmo com a leitura de 'a' ou 'b' c) Sequências que tenham o PREFIXO ab ou o SUFIXO ab (ou ambos) Para construir o AFD para essa linguagem, você precisa considerar os seguintes estados: - Estado inicial: q0 - Estado final: qf - Transições: - De q0 para si mesmo com a leitura de qualquer símbolo, exceto 'a' - De q0 para q1 com a leitura de 'a' - De q1 para si mesmo com a leitura de qualquer símbolo, exceto 'b' - De q1 para qf com a leitura de 'b' d) Sequências em que o PREFIXO de COMPRIMENTO DOIS coincide com o SUFIXO de COMPRIMENTO DOIS Para construir o AFD para essa linguagem, você precisa considerar os seguintes estados: - Estado inicial: q0 - Estado final: qf - Transições: - De q0 para si mesmo com a leitura de qualquer símbolo, exceto 'a' ou 'b' - De q0 para q1 com a leitura de 'a' ou 'b' - De q1 para si mesmo com a leitura de qualquer símbolo, exceto 'a' ou 'b' - De q1 para q2 com a leitura de 'a' ou 'b' - De q2 para si mesmo com a leitura de qualquer símbolo, exceto 'a' ou 'b' - De q2 para qf com a leitura de 'a' ou 'b' e) Sequências em que o número de ocorrências da subsequência ab seja igual ao número de ocorrências da subsequência ba Para construir o AFD para essa linguagem, é um pouco mais complexo e requer uma análise mais detalhada. Recomendo estudar sobre autômatos de pilha para resolver esse problema. Espero que isso ajude!
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Materiais relacionados
1 pág.
20 pág.
Compartilhar