Gramatika neograničenih produkcija

U teoriji formalnih jezika, gramatika neograničenih produkcija je formalna gramatika koja ne postavlja ograničenja na lijeve i desne strane produkcija. Ovo je najopćenitija klasa gramatika u Chomskyjevoj hijerarhiji koja može generirati proizvoljan rekurzivno prebrojiv jezik.

Formalna definicija

Gramatika neograničenih produkcija je formalna gramatika $G=(N,\Sigma ,P,S)$, gdje je $N$ skup nezavršnih znakova, $\Sigma$ skup završnih znakova, $N$ i $\Sigma$ su disjunktni skupovi (ustvari, ovo i nije nužno potrebno, pošto gramatike neograničenih produkcija ne razlikuju završne i nezavršne znakove, a oznake postoje iz jednostavnog razloga da se zna kad treba stati prilikom pokušaja generiranja rečeničnih oblika gramatike), $P$ je skup produkcija oblika $\alpha \to \beta$ pri čemu su $\alpha$ i $\beta$ nizovi znakova u $N\cup \Sigma$ i $\alpha$ nije prazni niz, te $S\in N$ specijalno označeni početni znak. Kao što samo ime implicira, ne postoje stvarna ograničenja nad tipovima produkcija dozvoljenih u gramatikama neograničenih produkcija.

Gramatike neograničenih produkcija i Turingovi strojevi

Može se pokazati da gramatike neograničenih produkcija opisuju rekurzivno prebrojive jezike. Ovo je kao da kažemo da za svaku gramatiku neograničenih produkcija $G$ postoji neki Turingov stroj koji prepoznaje $L(G)$, a vrijedi i obrat ove tvrdnje. Za danu gramatiku neograničenih produkcija takav je Turingov stroj jednostavno konstruirati, i to kao dvotračni nedeterministički Turingov stroj. Prva traka sadrži ulaznu riječ $w$ koju ispitivamo, dok stroj koristi drugu traku za generiranje rečeničnih oblika iz $G$. Turingov stroj potom radi sljedeće:

1. Započinje rad na krajnje lijevom kraju druge trake i potom ponavljajuće odabire pomak udesno ili odabire trenutnu poziciju na traci.
2. Nedeterministički odabire produkciju $\beta \to \gamma$ iz skupa produkcija gramatike $G$.
3. ako se $\beta$ pojavi na nekoj poziciji druge trake, zamijeni $\beta$ sa $\gamma$, uz mogući posmak znakova trake lijevo ili desno ovisno o relativnim duljinama $\beta$ i $\gamma$ (tj. ako je $\beta$ dulji od $\gamma$, obavi posmak znakova trake ulijevo).
4. Usporedi rezultirajući rečenični oblik na drugoj traci s riječi na prvoj traci. Ako odgovaraju, tada Turingov stroj prihvaća riječ. Ako ne odgovaraju, vrati se na prvi korak.

Lako se vidi da će ovaj Turingov stroj generirati sve i samo rečenične oblike gramatike $G$ na drugoj traci nakon što je posljednji korak izvršen proizvoljan broj puta, i time jezik $L(G)$ mora biti rekurzivno prebrojiv.

Obrnuta konstrukcija je također moguća. Za dani Turingov stroj, moguće je stvoriti gramatiku neograničenih produkcija.

Komputacijska svojstva

Kao što se može očekivati iz pokazane istovjetnosti gramatika neograničenih produkcija i Turingovih strojeva, problem odluke pripada li dani niz znakova $s$ jeziku neke gramatike neograničenih produkcija je općenito neodlučiv.

Savršeno je moguće stvoriti univerzalnu gramatiku neograničenih produkcija koja je sposobna prihvatiti jezik bilo koje druge gramatike neograničenih produkcija za dani opis samog jezika, baš kao što je moguće stvoriti univerzalni Turingov stroj, tako da bi u teoriji bilo moguće izgraditi programski jezik baziran na gramatikama neograničenih produkcija.

Izvori

• John Hopcroft i Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. 1st edition izdanje. Addison-Wesley. ISBN 0-201-44124-1 (the Cinderella book)

• Siniša Srbljić. 2003. Jezični procesori 1. Element. ISBN 953-197-129-3