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.
Formalna definicija
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.
Primjer
Jednostavna prefiksna gramatika definirana na sljedeći način:
generira jezik definiran sljedećim regularnim izrazom:
Kategorija:Formalni jezici