Příklad 1:

Navrhněte NFA pro tabulku přechodů, jak je uvedeno níže:

hashmap java

Řešení:

Diagram přechodu lze nakreslit pomocí funkce mapování, jak je uvedeno v tabulce.

Tady,

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

Příklad 2:

Navrhněte NFA s ∑ = {0, 1} akceptuje všechny řetězce končící na 01.

Řešení:

NFA by tedy bylo:

Příklad 3:

Navrhněte NFA s ∑ = {0, 1}, ve kterém dvojitá '1' následuje dvojitá '0'.

Řešení:

FA s double 1 je následující:

typ v jazyce Java

Bezprostředně po něm musí následovat dvojnásobek 0.

Pak,

Nyní před double 1 může být libovolný řetězec 0 a 1. Podobně po double 0 může být libovolný řetězec 0 a 1.

NFA se tedy stává:

Nyní uvažujeme řetězec 01100011

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

Příklad 4:

Navrhněte NFA, ve kterém celý řetězec obsahuje podřetězec 1110.

léčit nástroj gimp

Řešení:

Jazyk se skládá ze všech řetězců obsahujících podřetězec 1010. Diagram částečného přechodu může být:

Nyní jako podřetězec může být 1010. Proto přidáme vstupy 0 a 1, aby bylo možné zachovat podřetězec 1010 jazyka. NFA se tedy stává:

hiba bukhari

Přechodová tabulka pro výše uvedený přechodový diagram může být uvedena níže:

Uvažujme řetězec 111010,

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

Uvízl! Protože pro vstupní symbol 0 neexistuje cesta z q2. Řetězec 111010 můžeme zpracovat jiným způsobem.

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

Jako stav q5 je stav přijetí. Dostaneme kompletní skenování a dostali jsme se do konečného stavu.

Příklad 5:

Navrhněte NFA s ∑ = {0, 1} akceptuje všechny řetězce, ve kterých je třetí symbol od pravého konce vždy 0.

Řešení:

Třetí symbol tedy dostaneme z pravého konce jako '0' vždy. NFA může být:

Výše uvedený obrázek je NFA, protože ve stavu q0 se vstupem 0 můžeme přejít buď do stavu q0 nebo q1.