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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G=(N,\Sigma ,P,S)} , gdje je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle N} skup nezavršnih znakova, Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Sigma } skup završnih znakova, $N$ i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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), Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle P} je skup produkcija oblika Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha \to \beta } pri čemu su $\alpha$ i $\beta$ nizovi znakova u Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G} postoji neki Turingov stroj koji prepoznaje Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \beta \to \gamma } iz skupa produkcija gramatike Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} .
3. ako se Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} pojavi na nekoj poziciji druge trake, zamijeni Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} sa Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} , uz mogući posmak znakova trake lijevo ili desno ovisno o relativnim duljinama Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} (tj. ako je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} dulji od Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} , obavi posmak znakova trake ulijevo).
4. Usporedi rezultirajući rečenični oblik na drugoj traci sa 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} na drugoj traci nakon što je posljednji korak izvršen proizvoljan broj puta, i time jezik Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

• Nepoznat parametar: id

(the Cinderella book)

• Nepoznat parametar: id