Exemplo 1:
Projetar um FA com ∑ = {0, 1} aceita aquelas strings que começam com 1 e terminam com 0.
Solução:
O FA terá um estado inicial q0 a partir do qual apenas a aresta com entrada 1 irá para o próximo estado.
No estado q1, se lermos 1, estaremos no estado q1, mas se lermos 0 no estado q1, chegaremos ao estado q2 que é o estado final. No estado q2, se lermos 0 ou 1, iremos para o estado q2 ou q1, respectivamente. Observe que se a entrada terminar em 0, ela estará no estado final.
Exemplo 2:
Projetar um FA com ∑ = {0, 1} aceita a única entrada 101.
Solução:
Na solução dada, podemos ver que apenas a entrada 101 será aceita. Portanto, para a entrada 101, não há outro caminho mostrado para outra entrada.
matriz em string
Exemplo 3:
O projeto FA com ∑ = {0, 1} aceita um número par de 0 e um número par de 1.
Solução:
como obter pombo de jogo no android
Este FA considerará quatro estágios diferentes para a entrada 0 e a entrada 1. Os estágios podem ser:
Aqui q0 é um estado inicial e também o estado final. Observe cuidadosamente que uma simetria de 0 e 1 é mantida. Podemos associar significados a cada estado como:
q0: estado de número par de 0 e número par de 1.
q1: estado de número ímpar de 0 e número par de 1.
q2: estado de número ímpar de 0 e número ímpar de 1.
q3: estado de número par de 0 e número ímpar de 1.
Exemplo 4:
O projeto FA com ∑ = {0, 1} aceita o conjunto de todas as strings com três 0's consecutivos.
Solução:
As strings que serão geradas para esses idiomas específicos são 000, 0001, 1000, 10001, .... nas quais 0 sempre aparece em um grupo de 3. O gráfico de transição é o seguinte:
Observe que a sequência de zeros triplos é mantida para chegar ao estado final.
Exemplo 5:
Projete um AFD L(M) = {w | w ε {0, 1}*} e W é uma string que não contém 1's consecutivos.
Solução:
Quando ocorrerem três 1s consecutivos, o DFA será:
Aqui, dois 1's consecutivos ou um único 1 são aceitáveis, portanto
Os estágios q0, q1, q2 são os estados finais. O DFA irá gerar as strings que não contêm 1 consecutivos como 10, 110, 101,..... etc.
ciclo de vida do sdlc
Exemplo 6:
Projetar um FA com ∑ = {0, 1} aceita as strings com um número par de 0 seguidos por um único 1.
Solução:
O DFA pode ser mostrado por um diagrama de transição como:
