Razlika između inačica stranice »Prefiksna gramatika«
Izvor: Hrvatska internetska enciklopedija
(Bot: Automatski unos stranica) |
m (bnz) |
||
Redak 1: | Redak 1: | ||
U [[računarstvo|računarstvu]], '''prefiksna gramatika''' je gramatika srodna [[formalna gramatika|formalnim gramatikama]], u kojoj se nizovi znakova (stringovi) grade iz skupa baznih nizova znakova neprekidnom zamjenom prefiksa. Prefiksne gramatike opisuju točno sve [[regularni jezik|regularne jezike]]. | |||
== Formalna definicija == | == Formalna definicija == |
Trenutačna izmjena od 22:32, 11. travnja 2022.
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]