Введение
Теория языка В теории автоматов класс неограниченных грамматик (также называемых полу-Тюэ, тип 0 или грамматика структуры фраз) является наиболее общим классом грамматик в иерархии Чомского. Никаких ограничений не налагается на произведения с неограниченной грамматикой, за исключением того, что каждая из их левых сторон не пуста. является конечным набором правил производства в форме, где и является строкой символов в и не является пустой строкой, и является специально назначенным стартовым символом. Как следует из названия, нет никаких реальных ограничений на типы правил производства, которые могут иметь неограниченные грамматики.
In automata theory, the class of unrestricted grammars (also called semi Thue, type 0 or phrase structure grammars) is the most general class of grammars in the Chomsky hierarchy. No restrictions are made on the productions of an unrestricted grammar, other than each of their left hand sides being non empty. is a finite set of production rules of the form where and are strings of symbols in and is not the empty string, and
is a specially designated start symbol. As the name implies, there are no real restrictions on the types of production rules that unrestricted grammars can have.
Эквивалентность машинам Тьюринга
Неограниченные грамматики характеризуют рекурсивно перечисляемые языки. Это то же самое, что сказать, что для каждой неограниченной грамматики существует машина Тьюринга, способная распознавать и наоборот. При наличии неограниченной грамматики, такая машина Тьюринга достаточно проста в построении, как двухлентовая недетерминированная машина Тьюринга. Первая лента содержит входное слово, которое должно быть протестировано, а вторая лента используется машиной для генерации предложения из машины Тьюринга, затем делает следующее: Начните слева от второй ленты и неоднократно выбирайте перемещение вправо или выбирайте текущее положение на ленте. Недетерминированно выбирайте постановку из постановки в If, которая появляется в некотором месте на второй ленте, заменяйте в этой точке, возможно, смещая символы на ленте влево или вправо в зависимости от относительных длин и (например, если длиннее , смещайте символы ленты влево). Сравните полученную форму предложения на ленте 2 со словом на ленте 1. Если они совпадают, то машина Тьюринга принимает слово. Если они этого не сделают, машина Тьюринга вернется к первому шагу. Легко увидеть, что эта машина Тьюринга будет генерировать все и только предложения формы на его второй ленте после того, как последний шаг выполняется произвольное количество раз, таким образом, язык должен быть рекурсивно перечислимо. Обратная конструкция также возможна. При наличии некоторой машины Тьюринга можно создать эквивалентную неограниченную грамматику, которая даже использует только произведения с одним или несколькими нетерминальными символами на левой стороне. Поэтому произвольная неограниченная грамматика всегда может быть эквивалентно преобразована, чтобы подчиняться последней форме, преобразовав ее в машину Тьюринга и обратно. Некоторые авторы используют последнюю форму как определение неограниченной грамматики.
Start at the left of the second tape and repeatedly choose to move right or select the current position on the tape. Nondeterministically choose a production from the productions in If appears at some position on the second tape, replace by at that point, possibly shifting the symbols on the tape left or right depending on the relative lengths of and (e. g. if is longer than , shift the tape symbols left). Compare the resulting sentential form on tape 2 to the word on tape 1. If they match, then the Turing machine accepts the word. If they don't, the Turing machine will go back to step 1. It is easy to see that this Turing machine will generate all and only the sentential forms of on its second tape after the last step is executed an arbitrary number of times, thus the language must be recursively enumerable. The reverse construction is also possible. Given some Turing machine, it is possible to create an equivalent unrestricted grammar which even uses only productions with one or more non terminal symbols on their left hand sides. Therefore, an arbitrary unrestricted grammar can always be equivalently converted to obey the latter form, by converting it to a Turing machine and back again. Some authors use the latter form as definition of unrestricted grammar.
Вычислительные свойства
Проблема решения, может ли данная строка быть создана данной неограниченной грамматикой, эквивалентна проблеме, может ли она быть принята машиной Тьюринга, эквивалентной грамматике. Последняя проблема называется проблемой остановки и является нерешимой. Рекурсивно-перечисляемые языки закрыты под звездой Клине, конкатенцией, соединением и пересечением, но не под разницами множеств; см. Рекурсивно-перечисляемые языки#Свойства закрытия. Эквивалентность неограниченных грамматик с машинами Тьюринга подразумевает существование универсальной неограниченной грамматики, грамматики, способной принять любой другой язык неограниченной грамматики с учетом описания языка. По этой причине теоретически возможно создать язык программирования на основе неограниченных грамматик (например, Thue).