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 definicijaUredi

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 primjeniti samo na niz znakova oblika uw.

PrimjerUredi

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

  •  
  •  
  •  

generira jezik definiran sljedećim regularnim izrazom: