Gramatika neograničenih produkcija

Izvor: Wikipedija

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 | uredi kôd]

Gramatika neograničenih produkcija je formalna gramatika , gdje je skup nezavršnih znakova, skup završnih znakova, i 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), je skup produkcija oblika pri čemu su i nizovi znakova u i nije prazni niz, te 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 | uredi kôd]

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 postoji neki Turingov stroj koji prepoznaje , 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č koju ispitivamo, dok stroj koristi drugu traku za generiranje rečeničnih oblika iz . 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 iz skupa produkcija gramatike .
  3. ako se pojavi na nekoj poziciji druge trake, zamijeni sa , uz mogući posmak znakova trake lijevo ili desno ovisno o relativnim duljinama i (tj. ako je dulji od , 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 na drugoj traci nakon što je posljednji korak izvršen proizvoljan broj puta, i time jezik 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 | uredi kôd]

Kao što se može očekivati iz pokazane istovjetnosti gramatika neograničenih produkcija i Turingovih strojeva, problem odluke pripada li dani niz znakova 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 | uredi kôd]

  • John Hopcroft i Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation 1st edition izdanje. Addison-Wesley. ISBN 0-201-44124-1 |edition= sadrži dodatni tekst (pomoć) (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.