TechCodeview

Príklad 1:

Navrhnite NFA pre tabuľku prechodu, ako je uvedené nižšie:

Riešenie:

Diagram prechodu možno nakresliť pomocou funkcie mapovania, ako je uvedené v tabuľke.

Tu,

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

Príklad 2:

Navrhnite NFA s ∑ = {0, 1} akceptuje všetky reťazce končiace na 01.

Riešenie:

NFA by teda bolo:

Príklad 3:

Navrhnite NFA s ∑ = {0, 1}, v ktorom po dvojitej '1' nasleduje dvojitá '0'.

Riešenie:

FA s dvojitou 1 je nasledovná:

Bezprostredne za ním by mala nasledovať dvojitá 0.

potom

Teraz pred dvojitou 1 môže byť ľubovoľný reťazec 0 a 1. Podobne po dvojitej 0 môže byť ľubovoľný reťazec 0 a 1.

NFA sa teda stáva:

Teraz uvažujeme reťazec 01100011

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

Príklad 4:

Navrhnite NFA, v ktorom celý reťazec obsahuje podreťazec 1110.

Riešenie:

reťazec v porovnaní s

Jazyk pozostáva zo všetkých reťazcov obsahujúcich podreťazec 1010. Čiastočný prechodový diagram môže byť:

Teraz ako podreťazec môže byť 1010. Preto pridáme vstupy 0 a 1, aby bolo možné zachovať podreťazec 1010 jazyka. NFA sa teda stáva:

Prechodová tabuľka pre vyššie uvedený prechodový diagram môže byť uvedená nižšie:

Uvažujme reťazec 111010,

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

Uviazol! Keďže pre vstupný symbol 0 neexistuje cesta z q2. Reťazec 111010 môžeme spracovať aj iným spôsobom.

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

Ako stav q5 je stav prijatia. Získali sme kompletné skenovanie a dostali sme sa do konečného stavu.

Príklad 5:

Navrhnite NFA s ∑ = {0, 1} akceptuje všetky reťazce, v ktorých je tretí symbol od pravého konca vždy 0.

Riešenie:

Takto dostaneme tretí symbol z pravého konca ako '0' vždy. NFA môže byť:

Vyššie uvedený obrázok je NFA, pretože v stave q0 so vstupom 0 môžeme prejsť buď do stavu q0 alebo q1.