logo

Exempel på NFA

Exempel 1:

Designa en NFA för övergångstabellen enligt nedan:

Nuvarande tillstånd 0 1
→q0 q0, q1 q0, q2
q1 q3 e
q2 q2, q3 q3
→q3 q3 q3

Lösning:

Övergångsdiagrammet kan ritas genom att använda mappningsfunktionen enligt tabellen.

Exempel på NFA

Här,

rajesh khanna
 δ(q0, 0) = {q0, q1} δ(q0, 1) = {q0, q2} Then, δ(q1, 0) = {q3} Then, δ(q2, 0) = {q2, q3} δ(q2, 1) = {q3} Then, δ(q3, 0) = {q3} δ(q3, 1) = {q3} 

Exempel 2:

Designa en NFA med ∑ = {0, 1} accepterar alla strängar som slutar med 01.

Lösning:

Exempel på NFA

Därför skulle NFA vara:

linux-kommandon skapa mapp
Exempel på NFA

Exempel 3:

Designa en NFA med ∑ = {0, 1} där dubbel '1' följs av dubbel '0'.

Lösning:

FA med dubbel 1 är som följer:

Exempel på NFA

Den ska omedelbart följas av dubbel 0.

Sedan,

Exempel på NFA

Nu före dubbel 1 kan det finnas vilken sträng som helst med 0 och 1. På samma sätt, efter dubbel 0, kan det finnas vilken sträng som helst med 0 och 1.

Därför blir NFA:

Exempel på NFA

Överväger nu strängen 01100011

 q0 → q1 → q2 → q3 → q4 → q4 → q4 → q4 

Exempel 4:

Designa en NFA där all sträng innehåller en delsträng 1110.

datautvinning

Lösning:

Språket består av all sträng som innehåller delsträng 1010. Det partiella övergångsdiagrammet kan vara:

Exempel på NFA

Nu som 1010 kan vara delsträngen. Därför kommer vi att lägga till ingångarna 0:or och 1:or så att delsträngen 1010 för språket kan bibehållas. Därför blir NFA:

.net handledning
Exempel på NFA

Övergångstabell för ovanstående övergångsdiagram kan ges nedan:

Nuvarande tillstånd 0 1
→q1 q1 q1, q2
q2 q3
q3 q4
q4 q5
*q5 q5 q5

Tänk på en sträng 111010,

 δ(q1, 111010) = δ(q1, 1100) = δ(q1, 100) = δ(q2, 00) 

Fastnade! Eftersom det inte finns någon väg från q2 för ingångssymbol 0. Vi kan bearbeta sträng 111010 på ett annat sätt.

 δ(q1, 111010) = δ(q2, 1100) = δ(q3, 100) = δ(q4, 00) = δ(q5, 0) = δ(q5, ε) 

Som tillstånd q5 är accepttillståndet. Vi får den fullständiga skannade och vi nådde det slutliga tillståndet.

Exempel 5:

Designa en NFA med ∑ = {0, 1} accepterar alla strängar där den tredje symbolen från den högra änden alltid är 0.

Lösning:

Exempel på NFA

Således får vi den tredje symbolen från den högra änden som '0' alltid. NFA kan vara:

Exempel på NFA

Ovanstående bild är en NFA eftersom i tillstånd q0 med ingång 0, kan vi antingen gå till tillstånd q0 eller q1.