Граматика без ограничења

У теорији формалних језика, граматика без ограничења је формална граматика над којом нема ограничења у вези са левом и десном страном правила извођења. Ово је најопштија класа граматика у хијерархији Чомског-Шиценбергера, и може да генерише произвољне рекурзивно пребројиве језике.

Формална дефиниција

Граматика без ограничења је формална граматика $G=(N,\Sigma ,P,S)$, где је $N$ скуп незавршних симбола, $\Sigma$ је скуп завршних симбола, $N$ и $\Sigma$ су дисјунктни (у ствари, ово није строго неопходно, јер граматике без ограничења у суштини не праве разлику између завршних и незавршних симбола - разлика се прави само да би се знало када треба стати са генерисањем реченичних форми граматике), $P$ је скуп правила извођења облика $\alpha \to \beta$ где су $\alpha$ и $\beta$ ниске симбола из $N\cup \Sigma$, $\alpha$ није празна ниска, и $S\in N$ је посебно одабрани почетни симбол. Као што име наговештава, нема правих ограничења што се тиче типова правила извођења која граматика без ограничења може да садржи.

Граматике без ограничења и Тјурингове машине

Може да се покаже да граматике без ограничења одговарају рекурзивно пребројивим језицима. Ово значи да за сваку граматику без ограничења $G$ постоји нека Тјурингова машина која је способна да препозна $L(G)$ и обратно. За дату граматику без ограничења, такву Тјурингову машину је прилично једноставно конструисати, као недетерминистичку Тјурингову машину са две траке. Прва трака садржи улазну реч $w$, која се тестира, а другу траку машина користи да генерише реченичне форме из $G$. Тјурингова машина ради на следећи начин:

1. Креће слева на другој траци и узастопно бира да се помера удесно или да одабира тренутну позицију на траци.
2. Недетерминистички бира правило извођења $\beta \to \gamma$ из скупа правила из $G$.
3. Ако се $\beta$ појављује на некој позицији на другој траци, замењује $\beta$ са $\gamma$ на том месту, уз потенцијално померање симбола на траци улево или удесно, у зависности од релативних дужина $\beta$ и $\gamma$ (то јест, ако је $\beta$ дуже од $\gamma$, симболи на траци се померају улево).
4. Пореди се резултујућа реченична форма на другој траци са речју са прве траке 1. Ако се речи поклапају, Тјурингова машина прихвата реч. Ако се не поклапају, враћа се на први корак.

Лако се може видети да ова Тјурингова машина генерише све и тачно све реченичне форме за $G$ на својој другој траци након што је последњи корак извршен довољан број пута, и стога језик $L(G)$ мора да буде рекурзивно пребројив.

Могућа је и обратна конструкција. За дату Тјурингову машину је могуће направити одговарајућу граматику без ограничења.

Рачунска својства

Као што се може очекивати из еквиваленције граматика без ограничења и Тјурингових машина, проблем одлучивања да ли дата ниска $s$ припада језику неке граматике без ограничења је у општем случају неодлучив.

Потпуно је могуће да се направи универзална граматика без ограничења која је у стању да прихвати језик сваке друге граматике без ограничења за дати опис језика, као што је могуће да се направи универзална Тјурингова машина, па би у теорији било могуће да се направи програмски језик базиран на граматикама без ограничења (на пример Thue).

Види још

• Тјурингова машина
• Ламбда рачун

Литература

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