Eksempel 1:
Design en FA med ∑ = {0, 1} accepterer de strenge, der starter med 1 og slutter med 0.
Løsning:
FA'en vil have en starttilstand q0, hvorfra kun kanten med input 1 vil gå til den næste tilstand.
I tilstand q1, hvis vi læser 1, vil vi være i tilstand q1, men hvis vi læser 0 ved tilstand q1, vil vi nå til tilstand q2, som er den endelige tilstand. I tilstand q2, hvis vi læser enten 0 eller 1, vil vi gå til henholdsvis q2 tilstand eller q1 tilstand. Bemærk, at hvis input slutter med 0, vil det være i den endelige tilstand.
Eksempel 2:
Design en FA med ∑ = {0, 1} accepterer det eneste input 101.
Løsning:
I den givne løsning kan vi se, at kun input 101 vil blive accepteret. For input 101 er der derfor ingen anden vej vist for andet input.
Eksempel 3:
Design FA med ∑ = {0, 1} accepterer lige tal af 0'ere og lige tal af 1'ere.
Løsning:
Denne FA vil overveje fire forskellige trin for input 0 og input 1. Faserne kunne være:
Her er q0 en starttilstand og den endelige tilstand også. Bemærk nøje, at en symmetri af 0'er og 1'er opretholdes. Vi kan knytte betydninger til hver stat som:
q0: tilstand af lige antal 0'ere og lige antal 1'ere.
q1: tilstand af ulige antal 0'ere og lige antal 1'ere.
q2: tilstand af ulige antal 0'ere og ulige antal 1'ere.
q3: tilstand af lige antal 0'ere og ulige antal 1'ere.
Eksempel 4:
Design FA med ∑ = {0, 1} accepterer sættet af alle strenge med tre på hinanden følgende 0'er.
Løsning:
De strenge, der vil blive genereret for dette særlige sprog, er 000, 0001, 1000, 10001, .... hvor 0 altid vises i en klump af 3. Overgangsgrafen er som følger:
Bemærk, at sekvensen af tredobbelte nuller opretholdes for at nå den endelige tilstand.
Eksempel 5:
Design en DFA L(M) = {w | w ε {0, 1}*} og W er en streng, der ikke indeholder på hinanden følgende 1'ere.
Løsning:
Når tre på hinanden følgende 1'ere forekommer, vil DFA være:
Her er to på hinanden følgende 1'ere eller enkelt 1'ere acceptable, derfor
Trinene q0, q1, q2 er sluttilstandene. DFA genererer de strenge, der ikke indeholder på hinanden følgende 1'ere som 10, 110, 101 osv.
Eksempel 6:
Design en FA med ∑ = {0, 1} accepterer strengene med et lige tal på 0'er efterfulgt af enkelt 1.
Løsning:
DFA kan vises med et overgangsdiagram som:
