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

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

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

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^*$