Příklad 1:
Navrhněte FA s ∑ = {0, 1} akceptuje ty řetězce, které začínají 1 a končí 0.
Řešení:
FA bude mít počáteční stav q0, ze kterého přejde do dalšího stavu pouze hrana se vstupem 1.
Ve stavu q1, čteme-li 1, budeme ve stavu q1, ale čteme-li 0 ve stavu q1, dostaneme se do stavu q2, což je konečný stav. Pokud ve stavu q2 čteme buď 0 nebo 1, přejdeme do stavu q2 nebo q1. Všimněte si, že pokud vstup končí 0, bude v konečném stavu.
bubble sort java
Příklad 2:
Navrhněte FA s ∑ = {0, 1} akceptuje jediný vstup 101.
Řešení:
V daném řešení vidíme, že bude akceptován pouze vstup 101. Pro vstup 101 tedy není zobrazena žádná jiná cesta pro jiný vstup.
Příklad 3:
Návrh FA s ∑ = {0, 1} akceptuje sudý počet 0 a sudý počet jedniček.
Řešení:
Tento FA bude uvažovat čtyři různé stupně pro vstup 0 a vstup 1. Stupně mohou být:
Zde q0 je počáteční stav a také konečný stav. Pozorně si všimněte, že je zachována symetrie 0 a 1. Ke každému stavu můžeme přiřadit významy jako:
q0: stav sudého počtu 0 a sudého počtu jedniček.
q1: stav lichého počtu 0 a sudého počtu jedniček.
q2: stav lichého počtu 0 a lichého počtu 1.
q3: stav sudého počtu 0 a lichého počtu jedniček.
Příklad 4:
Design FA s ∑ = {0, 1} akceptuje množinu všech řetězců se třemi po sobě jdoucími nulami.
Řešení:
Řetězce, které budou vygenerovány pro tyto konkrétní jazyky, jsou 000, 0001, 1000, 10001, .... ve kterých se 0 vždy objeví ve shluku 3. Graf přechodu je následující:
Všimněte si, že posloupnost trojitých nul je zachována pro dosažení konečného stavu.
Příklad 5:
Navrhněte DFA L(M) = {w | w ε {0, 1}*} a W je řetězec, který neobsahuje po sobě jdoucí jedničky.
Řešení:
Když se objeví tři po sobě jdoucí jedničky, DFA bude:
plsql
Zde jsou přijatelné dvě po sobě jdoucí jedničky nebo jedna jednička
Stupně q0, q1, q2 jsou konečné stavy. DFA vygeneruje řetězce, které neobsahují po sobě jdoucí jedničky jako 10, 110, 101,..... atd.
Příklad 6:
Navrhněte FA s ∑ = {0, 1} akceptuje řetězce se sudým číslem 0 následovaným jednoduchou 1.
Řešení:
DFA lze zobrazit přechodovým diagramem jako:
