Prijeđi na sadržaj

Prefiksna gramatika

Izvor: Wikipedija

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

[uredi | uredi kôd]

Prefiksna gramatika G je uređena trojka gdje je

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

Svaka produkcija se može primijeniti samo na niz znakova oblika uw.

Primjer

[uredi | uredi kôd]

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

generira jezik definiran sljedećim regularnim izrazom: