Exempel 1:

Designa en FA med ∑ = {0, 1} accepterar de strängar som börjar med 1 och slutar med 0.

Lösning:

FA kommer att ha ett starttillstånd q0 från vilket endast kanten med ingång 1 kommer att gå till nästa tillstånd.

knn

I tillstånd q1, om vi läser 1, kommer vi att vara i tillstånd q1, men om vi läser 0 vid tillstånd q1, kommer vi att nå tillstånd q2 som är sluttillståndet. I tillstånd q2, om vi läser antingen 0 eller 1, kommer vi att gå till q2-tillstånd respektive q1-tillstånd. Observera att om ingången slutar med 0, kommer den att vara i sluttillståndet.

Exempel 2:

Designa en FA med ∑ = {0, 1} accepterar den enda ingången 101.

Lösning:

I den givna lösningen kan vi se att endast ingång 101 kommer att accepteras. För ingången 101 visas således ingen annan väg för annan ingång.

Exempel 3:

Design FA med ∑ = {0, 1} accepterar ett jämnt antal nollor och ett jämnt antal ettor.

Lösning:

Denna FA kommer att överväga fyra olika steg för ingång 0 och ingång 1. Stegen kan vara:

Här är q0 ett starttillstånd och sluttillståndet också. Observera noga att en symmetri av 0:or och 1:or bibehålls. Vi kan associera betydelser till varje stat som:

q0: tillstånd för jämna antal nollor och jämna antal ettor.
q1: tillstånd av udda antal 0:or och jämna antal 1:or.
q2: tillstånd av udda antal 0:or och udda antal 1:or.
q3: tillstånd av jämna antal nollor och udda antal ettor.

Exempel 4:

Design FA med ∑ = {0, 1} accepterar uppsättningen av alla strängar med tre på varandra följande nollor.

Lösning:

Strängarna som kommer att genereras för just detta språk är 000, 0001, 1000, 10001, .... där 0 alltid visas i en klump av 3. Övergångsdiagrammet är som följer:

Observera att sekvensen av trippelnollor bibehålls för att nå det slutliga tillståndet.

Exempel 5:

Designa en DFA L(M) = {w | w ε {0, 1}*} och W är en sträng som inte innehåller på varandra följande 1:or.

Lösning:

När tre på varandra följande 1:or inträffar blir DFA:

urfi javed

Här är två på varandra följande 1:or eller singel 1 acceptabelt, därför

Stegen q0, q1, q2 är sluttillstånden. DFA kommer att generera strängar som inte innehåller på varandra följande 1:or som 10, 110, 101,..... etc.

Exempel 6:

Designa en FA med ∑ = {0, 1} accepterar strängarna med ett jämnt antal nollor följt av enkel 1.

Lösning:

DFA kan visas med ett övergångsdiagram som: