Gramatika bez ograničenja

U teoriji formalnih jezika, gramatika bez ograničenja je formalna gramatika nad kojom nema ograničenja u vezi sa levom i desnom stranom pravila izvođenja. Ovo je najopštija klasa gramatika u hijerarhiji Čomskog-Šicenbergera, i može da generiše proizvoljne rekurzivno prebrojive jezike.

Formalna definicija

Gramatika bez ograničenja je formalna gramatika $G=(N,\Sigma ,P,S)$, gde je $N$ skup nezavršnih simbola, $\Sigma$ je skup završnih simbola, $N$ i $\Sigma$ su disjunktni (u stvari, ovo nije strogo neophodno, jer gramatike bez ograničenja u suštini ne prave razliku između završnih i nezavršnih simbola - razlika se pravi samo da bi se znalo kada treba stati sa generisanjem rečeničnih formi gramatike), $P$ je skup pravila izvođenja oblika $\alpha \to \beta$ gde su $\alpha$ i $\beta$ niske simbola iz $N\cup \Sigma$, $\alpha$ nije prazna niska, i $S\in N$ je posebno odabrani početni simbol. Kao što ime nagoveštava, nema pravih ograničenja što se tiče tipova pravila izvođenja koja gramatika bez ograničenja može da sadrži.

Gramatike bez ograničenja i Tjuringove mašine

Može da se pokaže da gramatike bez ograničenja odgovaraju rekurzivno prebrojivim jezicima. Ovo znači da za svaku gramatiku bez ograničenja $G$ postoji neka Tjuringova mašina koja je sposobna da prepozna $L(G)$ i obratno. Za datu gramatiku bez ograničenja, takvu Tjuringovu mašinu je prilično jednostavno konstruisati, kao nedeterminističku Tjuringovu mašinu sa dve trake. Prva traka sadrži ulaznu reč $w$, koja se testira, a drugu traku mašina koristi da generiše rečenične forme iz $G$. Tjuringova mašina radi na sledeći način:

1. Kreće sleva na drugoj traci i uzastopno bira da se pomera udesno ili da odabira trenutnu poziciju na traci.
2. Nedeterministički bira pravilo izvođenja $\beta \to \gamma$ iz skupa pravila iz $G$.
3. Ako se $\beta$ pojavljuje na nekoj poziciji na drugoj traci, zamenjuje $\beta$ sa $\gamma$ na tom mestu, uz potencijalno pomeranje simbola na traci ulevo ili udesno, u zavisnosti od relativnih dužina $\beta$ i $\gamma$ (to jest, ako je $\beta$ duže od $\gamma$, simboli na traci se pomeraju ulevo).
4. Poredi se rezultujuća rečenična forma na drugoj traci sa rečju sa prve trake 1. Ako se reči poklapaju, Tjuringova mašina prihvata reč. Ako se ne poklapaju, vraća se na prvi korak.

Lako se može videti da ova Tjuringova mašina generiše sve i tačno sve rečenične forme za $G$ na svojoj drugoj traci nakon što je poslednji korak izvršen dovoljan broj puta, i stoga jezik $L(G)$ mora da bude rekurzivno prebrojiv.

Moguća je i obratna konstrukcija. Za datu Tjuringovu mašinu je moguće napraviti odgovarajuću gramatiku bez ograničenja.

Računska svojstva

Kao što se može očekivati iz ekvivalencije gramatika bez ograničenja i Tjuringovih mašina, problem odlučivanja da li data niska $s$ pripada jeziku neke gramatike bez ograničenja je u opštem slučaju neodlučiv.

Potpuno je moguće da se napravi univerzalna gramatika bez ograničenja koja je u stanju da prihvati jezik svake druge gramatike bez ograničenja za dati opis jezika, kao što je moguće da se napravi univerzalna Tjuringova mašina, pa bi u teoriji bilo moguće da se napravi programski jezik baziran na gramatikama bez ograničenja (na primer Thue).

Vidi još

• Tjuringova mašina
• Lambda račun

Literatura

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