Exemple 1:
Dissenyar un FA amb ∑ = {0, 1} accepta aquelles cadenes que comença per 1 i acaba amb 0.
Solució:
instanciació en java
El FA tindrà un estat inicial q0 a partir del qual només la vora amb l'entrada 1 passarà al següent estat.
A l'estat q1, si llegim 1, estarem en l'estat q1, però si llegim 0 a l'estat q1, arribarem a l'estat q2 que és l'estat final. A l'estat q2, si llegim 0 o 1, passarem a l'estat q2 o a l'estat q1 respectivament. Tingueu en compte que si l'entrada acaba amb 0, estarà en l'estat final.
Exemple 2:
Dissenyar un FA amb ∑ = {0, 1} accepta l'única entrada 101.
Solució:
En la solució donada, podem veure que només s'acceptarà l'entrada 101. Per tant, per a l'entrada 101, no hi ha cap altre camí mostrat per a una altra entrada.
Exemple 3:
El disseny FA amb ∑ = {0, 1} accepta un nombre parell de 0 i un nombre parell d'1.
Solució:
fizzbuzz java
Aquest FA considerarà quatre etapes diferents per a l'entrada 0 i l'entrada 1. Les etapes podrien ser:
Aquí q0 és un estat inicial i també l'estat final. Tingueu en compte que es manté una simetria de 0 i 1. Podem associar significats a cada estat com:
q0: estat de nombre parell de 0 i nombre parell d'1.
q1: estat de nombre imparell de 0 i parell d'1.
q2: estat de nombre senar de 0 i senar d'1.
q3: estat de nombre parell de 0 i senar d'1.
Exemple 4:
El disseny FA amb ∑ = {0, 1} accepta el conjunt de totes les cadenes amb tres 0 consecutius.
Solució:
Les cadenes que es generaran per a aquests llenguatges concrets són 000, 0001, 1000, 10001, .... en les quals 0 sempre apareix en un grup de 3. El gràfic de transició és el següent:
Tingueu en compte que la seqüència de zeros triples es manté per arribar a l'estat final.
Exemple 5:
Dissenyeu un DFA L(M) = {w | w ε {0, 1}*} i W és una cadena que no conté uns consecutius.
Solució:
java invertint una cadena
Quan es produeixin tres 1 consecutius, el DFA serà:
Aquí s'accepten dos 1 consecutius o 1 únic, per tant
Les etapes q0, q1, q2 són els estats finals. El DFA generarà les cadenes que no continguin 1 consecutiu com 10, 110, 101,..... etc.
Exemple 6:
Dissenyar un FA amb ∑ = {0, 1} accepta les cadenes amb un nombre parell de 0 seguits d'1 únic.
Solució:
El DFA es pot mostrar mitjançant un diagrama de transició com:
