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.
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:
Derfor vil NFA være:
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:
Den skal umiddelbart etterfølges av dobbel 0.
Deretter,
annet hvis java
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:
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:
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:
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:
Dermed får vi det tredje symbolet fra høyre ende som '0' alltid. NFA kan være:
legge inn streng i java
Bildet ovenfor er en NFA fordi i tilstand q0 med inngang 0, kan vi enten gå til tilstand q0 eller q1.