Prefiksna gramatika
Izgled
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.
Prefiksna gramatika G je uređena trojka 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 primijeniti samo na niz znakova oblika uw.
Jednostavna prefiksna gramatika definirana na sljedeći način:
generira jezik definiran sljedećim regularnim izrazom: