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: