Prefiksna gramatika

Izvor: Wikipedija

U računarstvu, prefiksna gramatika je gramatika srodna formalnim gramatikama, u kojoj se nizovi znakova (stringovi) grade iz skupa baznih nizova znakova neprekidnom zamjenom prefiksa. Prefiksne gramatike opisuju točno sve regularne jezike.

[uredi] Formalna definicija

Prefiksna gramatika G je uređena trojka (Σ,S,P) gdje je

  • Σ konačna abeceda
  • S konačan skup baznih nizova znakova nad abecedom Σ
  • P skup produkcija oblika u \to v, gdje su u i v nizovi znakova nad Σ.

Svaka produkcija u \to v se može primjeniti samo na niz znakova oblika uw.

[uredi] Primjer

Jednostavna prefiksna gramatika definirana na sljedeći način:

  • \Sigma  = \left\{ {0,1} \right\}
  • S = \left\{ {01,10} \right\}
  • P = \left\{0 \to 010, 10 \to 100\right\}

generira jezik definiran sljedećim regularnim izrazom:

 01(01)^* \cup 100^*
Drugi jezici