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

Из Википедије, слободне енциклопедије

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

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

Граматика без ограничења је формална граматика 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).

Види још[уреди]


Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.


Литература[уреди]

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