1. példa:
Tervezze meg az NFA-t az átmeneti táblázathoz az alábbiak szerint:
| Jelen állapot | 0 | 1 |
|---|---|---|
| →q0 | q0, q1 | q0, q2 |
| q1 | q3 | e |
| q2 | q2, q3 | q3 |
| →q3 | q3 | q3 |
Megoldás:
Az átmenet diagram a táblázatban megadott leképezési függvény segítségével rajzolható meg.
Itt,
δ(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} 2. példa:
A ∑ = {0, 1} NFA tervezése minden 01-re végződő karakterláncot elfogad.
0,0625 törtként
Megoldás:
Tehát az NFA a következő lenne:
3. példa:
Tervezz meg egy NFA-t ∑ = {0, 1} értékkel, amelyben a dupla '1'-t dupla '0' követi.
Megoldás:
Az FA dupla 1-gyel a következő:
Közvetlenül utána dupla 0 kell.
Akkor,
Most a double 1 előtt tetszőleges 0 és 1 karakterlánc lehet. Hasonlóképpen a dupla 0 után bármilyen 0 és 1 karakterlánc lehet.
Így az NFA:
Most figyelembe véve a 01100011 karakterláncot
q0 → q1 → q2 → q3 → q4 → q4 → q4 → q4
4. példa:
Tervezzen meg egy NFA-t, amelyben az összes karakterlánc tartalmaz egy 1110-es karakterláncot.
Megoldás:
Linux futtatni cmd
A nyelv az 1010-es részstringet tartalmazó összes karakterláncból áll. A részleges átmenet diagram lehet:
Most 1010 lehet az alkarakterlánc. Ezért hozzáadjuk a 0 és 1 bemeneteket, hogy a nyelv 1010-es részkarakterlánca megmaradjon. Így az NFA:
A fenti átmeneti diagram átmeneti táblázata az alábbiakban adható meg:
| Jelen állapot | 0 | 1 |
|---|---|---|
| →q1 | q1 | q1, q2 |
| q2 | q3 | |
| q3 | q4 | |
| q4 | q5 | *q5 | q5 | q5 |
Vegyünk egy 111010 karakterláncot,
δ(q1, 111010) = δ(q1, 1100) = δ(q1, 100) = δ(q2, 00)
Megrekedt! Mivel a q2-ből nincs elérési út a 0 bemeneti szimbólumhoz. Az 111010 karakterláncot más módon is feldolgozhatjuk.
δ(q1, 111010) = δ(q2, 1100) = δ(q3, 100) = δ(q4, 00) = δ(q5, 0) = δ(q5, ε)
Mivel a q5 állapot az elfogadási állapot. Megkapjuk a teljes szkennelést, és elértük a végső állapotot.
5. példa:
Tervezze meg az NFA-t ∑ = {0, 1} értékkel, amely minden olyan karakterláncot elfogad, amelyben a harmadik szimbólum a jobb végétől mindig 0.
középső kép css-ben
Megoldás:
Így a harmadik szimbólumot mindig '0'-ként kapjuk a jobb oldalról. Az NFA lehet:
A fenti kép egy NFA, mert q0 állapotban 0 bemenettel q0 vagy q1 állapotba léphetünk.