Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
‘) Cm. прим. 2 к стр. 285 русского перевода работы [8 J.- Прим. пері».
Формальные свойства грамматик
163
работу в начальном состоянии S0, находясь против самого левого-вхождения 1 на ленте, и продолжает до тех пор, пока не закончит ее в выделенном заключительном состоянии Sf- К этому моменту на ленте содержится цепочка <р, окаймленная символами #, причем <р содержит j вхождений символа 1 и k вхождений символа е. Можно перестроить M так, что она не придеї в состояние Sf , пока не будет У>1, и без потери общности можно предположить, что, когда M пришла в состояние Sf , она находится против самого левого символа, отличного от , и что все вхождения 1 предшествуют всем вхождениям е (проще говоря, мы всегда можем добавить к любой машине M добавочный компонент, который автоматически переведет ее в эту заключительную конфигурацию, после того как она закончит свою работу). Тогда выходом М, если только M достигает состояния Sf, начиная с выхода Iі, будет цепочка V 1, /г>0). Мы уже видели (разд. 1.2), что для некоторых (а может быть, и для всех) входов M никогда не закончит свою работу и что невозможен алгоритм, определяющий по правилам М, закончит ли она работу при заданном входе и даже есть ли такой вход, при котором она закончит работу. Если M кончает работу при входе If с выходом Vek, то мы говорим, что M отображает число і в число j. Это описание носит самый общий характер, и любая машина Тьюринга, представляющая частичную функцию (т.е. функцию,которая может не быть определена для некоторых элементов области задания этой функции), отображающую целые положительные числа на целые положительные числа, может быть описана таким образом. Хорошо известно, что область определения так описанной машины Тьюринга есть ргкурсивно-перечислимое множество и что каждое рекурсивно-перечислимое множество является областью определения для некоторой машины Тьюринга.
Заметим, что такая машина Тьюринга никогда не пишет символа #, хотя она может читать и стирать этот символ (расширяя тем самым кусок ленты, доступный для вычислений). Следовательно,, если M при входе Iі кончает работу с выходом Vek, то /-)-К>?. Далее, непосредственно видно, что если, подобно тому как описано в разд. 2, мы построим множество правил подстановки, точно отражающее поведение М, то эти правила будут составлять моногенную грамматику G типа 1. Условие 1 будет выполнено в силу того, что-кусок ленты, используемой к данному моменту, никогда не уменьшается. Если M получает выход Vek при входе Iі , то G выдаст (#S0li#)-BHBOA, заканчивающийся цепочкой #SfW*#, и обратно. Хотя M может перечислять любое рекурсивно-перечислимое множество (как область определения представляемой ею функции), множество выходов, которые она порождает, рекурсивно.
Предположим теперь, что мы выбираем машину Тьюринга и сопоставляем ей грамматику G только что описанным способом.
.164
И. Хомский
Допустим далее, что мы строим грамматику G*, которая содержит все правила G1 и еще следующие четыре правила для порождения «начальных цепочек», необходимых для G:
S-J-S0I, S-vS.l, /ion
So-VS0I, Se-^SeI.
:Эти правила позволяют дать законченный (#5#)-вывод каждой цепочки вида #S01*#, где />-1, и только таких цепочек. Следовательно, полная грамматика G* будет давать законченный (#S#)-Bbi-вод цепочки #ц># тогда и только тогда, когда у =Sp Vek (/>- 1), п .для некоторого /, M при заданном входе Iі заканчивает работу с выходом Vek. Итак, для произвольной машины Тьюринга, перечисляющей рекурсивно-перечислимое множество S в качестве своей области определения, мы можем построить грамматику типа 1, которая порождает те и только те цепочки вида для ко-
торых <р?Ё, а ф есть цгпочка символов е (длина которой, впрочем, определяется цепочкой ср, гдеср^Е). Известно, что проблема распознавания для произвольной машины Тьюринга, является ли ¦ее область определения пустой, конечной или бесконечной, алгоритмически неразрешима. Следовательно, соответствующие проблемы .для грамматик типа 1 также алгоритмически неразрешимы.
Теорема 9. Невозможен алгоритм, распознающий по произвольной грамматике типа 1, порождает ли она пустое множество, порождает ли она конечное множество или бесконечное множество .цепочек [58].
По этой же самой причине невозможен алгоритм, определяющий, появляется ли данная цепочка как собственная часть строки .(#5#)-вывода в G. Далее, поскольку грамматика не дает никаких законченных (#5#)-выводов тогда, когда она эквивалентна грамматике G„mi с единственным правилом S—>-IS1 х), то по теореме 9 невозможно определить, эквивалентна ли грамматика G грамматике GmllI, а значит, и в общем случае.
Теорема 10. Невозможен алгоритм, определяющий эквивалентны ли заданные две грамматики типа 1 1581.
Впрочем, для любой алгоритмически неразрешимой проблемы машины Тьюринга можно найти аналогичную неразрешимую проблему, касающуюся грамматик типа 1. Другими словами, мало что можно узнать о свойствах языка, порождаемого грамматикой типа 1 (кроме того, что этот язык непременно рекурсивен), путем систематического исследования правил этой грамматики.
