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
, gdje su u i v nizovi znakova nad Σ.
Svaka produkcija se može primjeniti samo na niz znakova oblika uw.
[uredi] Primjer
Jednostavna prefiksna gramatika definirana na sljedeći način:
generira jezik definiran sljedećim regularnim izrazom:
