Prefiksna gramatika

Izvor: Hrvatska internetska enciklopedija
Inačica 475587 od 11. travnja 2022. u 22:32 koju je unio WikiSysop (razgovor | doprinosi) (bnz)
(razl) ←Starija inačica | vidi trenutačnu inačicu (razl) | Novija inačica→ (razl)
Skoči na:orijentacija, traži

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]