8. feladat: Jobbreguláris nyelvtanból véges automata

Eredeti feladat

Adott egy jobbreguláris nyelvtan szabályrendszere (pl. S -> aS, S -> aB, A -> b, stb.). Készítsük el az automatát!

Az automata rajza

graph LR Start(( )) --> S((S)) S -- "a" --> S S -- "a" --> B((B)) S -- "c" --> A((A)) A -- "c" --> A A -- "b" --> E(((E))) B -- "c" --> S B -- "a" --> E(((E))) A -- "b" --> B A -- "c" --> B A -- "b" --> C((C)) B -- "a" --> C((C)) C -- "a" --> E(((E))) C -- "b" --> B

Megoldás menete (Logika)

  1. Állapotok: Minden nemterminális szimbólum (S, A, B, C) egy állapot az automatában.
  2. Új végállapot: Vegyél fel egy extra végállapotot (pl. E vagy F), ami a szavak végét jelzi.
  3. Átmenetek (szabályból él):
    • Ha a szabály A -> aB, akkor az A állapotból 'a' jelre a B állapotba megyünk.
    • Ha a szabály A -> a, akkor az A állapotból 'a' jelre az E (végállapotba) megyünk.
  4. Kezdőállapot: A nyelvtan kezdőszimbóluma (S) lesz az automata kezdőállapota.

Felkészülés más számokra

Ha a szabályok változnak: