Gramatika neograničenih produkcija

Izvor: Wikipedija
Skoči na: orijentacija, traži

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[uredi VE | uredi]

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[uredi VE | uredi]

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. Ukoliko 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 sa riječi na prvoj traci. Ukoliko odgovaraju, tada Turingov stroj prihvaća riječ. Ukoliko 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[uredi VE | uredi]

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[uredi VE | uredi]

  • John Hopcroft i Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation, 1st edition, Addison-Wesley. ISBN 0-201-44124-1. (the Cinderella book)
Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.