Eksempel 1:
Design en FA med ∑ = {0, 1} godtar de strengene som starter med 1 og slutter med 0.
Løsning:
FA vil ha en starttilstand q0 hvorfra kun kanten med inngang 1 vil gå til neste tilstand.
I tilstand q1, hvis vi leser 1, vil vi være i tilstand q1, men hvis vi leser 0 ved tilstand q1, vil vi nå tilstand q2 som er den endelige tilstanden. I tilstand q2, hvis vi leser enten 0 eller 1, vil vi gå til henholdsvis q2 tilstand eller q1 tilstand. Merk at hvis inngangen ender med 0, vil den være i den endelige tilstanden.
Eksempel 2:
Design en FA med ∑ = {0, 1} aksepterer den eneste inngangen 101.
Løsning:
I den gitte løsningen kan vi se at kun input 101 vil bli akseptert. For inngang 101 er det derfor ingen annen vei vist for annen inngang.
Eksempel 3:
Design FA med ∑ = {0, 1} aksepterer partall på 0-ere og partall på 1-ere.
Løsning:
Denne FA vil vurdere fire forskjellige trinn for inngang 0 og inngang 1. Stadiene kan være:
Her er q0 en starttilstand og slutttilstanden også. Merk nøye at en symmetri av 0-er og 1-er opprettholdes. Vi kan knytte betydninger til hver stat som:
q0: tilstand av partall av 0-ere og partall av 1-er.
q1: tilstand av oddetall på 0-ere og partall på 1-ere.
q2: tilstand av oddetall på 0-ere og oddetall på 1-ere.
q3: tilstand av partall av 0-ere og oddetall av 1-er.
Eksempel 4:
Design FA med ∑ = {0, 1} godtar settet med alle strenger med tre påfølgende 0-er.
Løsning:
Strengene som vil bli generert for dette bestemte språket er 000, 0001, 1000, 10001, .... der 0 alltid vises i en klump av 3. Overgangsgrafen er som følger:
Merk at sekvensen av trippelnuller opprettholdes for å nå den endelige tilstanden.
Eksempel 5:
Design en DFA L(M) = {w | w ε {0, 1}*} og W er en streng som ikke inneholder påfølgende 1-ere.
Løsning:
Når tre påfølgende 1-er oppstår, vil DFA være:
Her er to påfølgende 1-ere eller enkelt 1 akseptable, derfor
Trinnene q0, q1, q2 er slutttilstandene. DFA vil generere strengene som ikke inneholder påfølgende 1-er som 10, 110, 101,..... osv.
Eksempel 6:
Design en FA med ∑ = {0, 1} aksepterer strengene med et partall på 0-er etterfulgt av enkelt 1.
Løsning:
DFA kan vises med et overgangsdiagram som:
