logo

Eksempler på NFA

Eksempel 1:

Design en NFA for overgangstabellen som gitt nedenfor:

Nåværende tilstand 0 1
→q0 q0, q1 q0, q2
q1 q3 e
q2 q2, q3 q3
→q3 q3 q3

Løsning:

Overgangsdiagrammet kan tegnes ved å bruke kartfunksjonen som gitt i tabellen.

Eksempler på NFA

Her,

 δ(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} 

Eksempel 2:

Design en NFA med ∑ = {0, 1} godtar all streng som slutter med 01.

Løsning:

Eksempler på NFA

Derfor vil NFA være:

Eksempler på NFA

Eksempel 3:

Design en NFA med ∑ = {0, 1} der dobbel '1' er etterfulgt av dobbel '0'.

Løsning:

FA med dobbel 1 er som følger:

Eksempler på NFA

Den skal umiddelbart etterfølges av dobbel 0.

Deretter,

annet hvis java
Eksempler på NFA

Nå før dobbel 1 kan det være en hvilken som helst streng på 0 og 1. På samme måte kan det være en hvilken som helst streng på 0 og 1 etter dobbel 0.

Derfor blir NFA:

Eksempler på NFA

Vurderer nå strengen 01100011

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

Eksempel 4:

Design en NFA der alle strengene inneholder en delstreng 1110.

Løsning:

Språket består av all strengen som inneholder delstreng 1010. Det delvise overgangsdiagrammet kan være:

Eksempler på NFA

Nå som 1010 kan være understrengen. Derfor vil vi legge til inngangene 0-er og 1-er slik at understrengen 1010 til språket kan opprettholdes. Derfor blir NFA:

Eksempler på NFA

Overgangstabell for overgangsdiagrammet ovenfor kan gis nedenfor:

Nåværende tilstand 0 1
→q1 q1 q1, q2
q2 q3
q3 q4
q4 q5
*q5 q5 q5

Tenk på en streng 111010,

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

Ble sittende fast! Siden det ikke er noen vei fra q2 for inngangssymbol 0. Vi kan behandle streng 111010 på en annen måte.

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

Som tilstand q5 er aksepttilstanden. Vi får hele skanningen, og vi nådde den endelige tilstanden.

Eksempel 5:

Design en NFA med ∑ = {0, 1} aksepterer alle strenger der det tredje symbolet fra høyre ende alltid er 0.

Løsning:

Eksempler på NFA

Dermed får vi det tredje symbolet fra høyre ende som '0' alltid. NFA kan være:

legge inn streng i java
Eksempler på NFA

Bildet ovenfor er en NFA fordi i tilstand q0 med inngang 0, kan vi enten gå til tilstand q0 eller q1.