Prefiksna gramatika
Izvor: Hrvatska internetska enciklopedija
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 [math]\displaystyle{ (\Sigma, S, P) }[/math] gdje je
- [math]\displaystyle{ \Sigma }[/math] konačna abeceda
- S konačan skup baznih nizova znakova nad abecedom [math]\displaystyle{ \Sigma }[/math]
- P skup produkcija oblika [math]\displaystyle{ u \to v }[/math], gdje su u i v nizovi znakova nad [math]\displaystyle{ \Sigma }[/math].
Svaka produkcija [math]\displaystyle{ u \to v }[/math] se može primjeniti samo na niz znakova oblika uw.
Primjer
Jednostavna prefiksna gramatika definirana na sljedeći način:
- [math]\displaystyle{ \Sigma = \left\{ {0,1} \right\} }[/math]
- [math]\displaystyle{ S = \left\{ {01,10} \right\} }[/math]
- [math]\displaystyle{ P = \left\{0 \to 010, 10 \to 100\right\} }[/math]
generira jezik definiran sljedećim regularnim izrazom:
- [math]\displaystyle{ 01(01)^* \cup 100^* }[/math]