Prefiksna gramatika

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 $(\mathrm{\Sigma },S,P)$ gdje je

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

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

Primjer

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

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

generira jezik definiran sljedećim regularnim izrazom:

$01(01{)}^{*}\cup 100^{*}$