Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Алфавит: {a, b, h};
Аксиома: Ah;
(NC)
Продукции: {GthP -> PhHl| 1<г</г},
aP -> Pa, bP-*Pb, HP Ph. Проблема останобки машины Тьюринга
Проблема тождества \для полутуэвст системы
Проблема \ ( Проблема тождества ] / тождества \для нормальнойJI для туэвской системы J \ системы
Проблема [соответствий Поста
'/Лро5лет~' тождества [для полигриппы,1
определенной соотношениями J Туэ
') Рассматриваются ниже, в гл. VIII. Г л. VI. Комбинаторные системы и машины Тьюринга
111
Продукции системы (NC) имеют вид
[KiP^PKill <г<п + 3}.
Провести сравнение проблемы тождества для (NC) с псевдопо-стовской проблемой; показать, что неравенства здесь оказываются излишними. Использовать число вхождений маркера h.
Б. Теперь нам надо устранить слова А и В, вернее, —Ah и Bh.
Будем исходить из «псевдопостовского равенства». Закодируем все элементы таким образом, чтобы получить независимое равенство слов А и В (равенство Поста); можно показать, что оно осуществляется лишь одновременно с псевдопостовским равенством.
Введем п + 5 пар слов (Fit Fi):
если K1 = x1x2 ... хр, то F1 = x1 kx2k ... xpk\
если Ki = D1IJ2 ... У р, то Fi = kyyky2 ... kyp,
где Xj, yj е {a, b, h} и k — некоторая новая буква. Последовательности Ah = xix2 ... xj сопоставляется пара
(Fn+4' Fn+4) = kkx2 . . . kXf).
Последовательности Eh = уіу2 . • • Уз сопоставляется пара (Fn+5, Fn+5) = (y1ky2k ... у/kk, kk).
Проделанные построения позволяют доказать наше предложение путем анализа возможных случаев. Следует воспользоваться методом доказательства от противного, рассматривая расположение вхождений k в интересующие нас слова. Часть И НЕКОТОРЫЕ ЗАМЕЧАТЕЛЬНЫЕ КЛАССЫ ЯЗЫКОВ
Глава VII
КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ (ЯЗЫКИ ХОМСКОГО):
ОБЩАЯ ХАРАКТЕРИСТИКА И ОСНОВНЫЕ СВОЙСТВА
§ 7.1. ГРАММАТИКА И ОПИСАНИЕ СИНТАКСИЧЕСКИХ СТРУКТУР
В начальных главах книги мы определяли язык как часть свободной полугруппы, порождаемой буквами некоторого алфавита (словами некоторого словаря) и грамматикой, выступающей как алгоритм, который позволяет перечислять слова (фразы) языка. Уточнения, которые мы внесли затем в представление об алгоритмах, дают нам возможность сформулировать ряд весьма общих результатов, относящихся к грамматикам и языкам.
7.1.1. Грамматики и машины Тьюринга
Итак, мы рассматриваем грамматику как алгоритм1), а понятие алгоритма отождествляем с понятием машины Тьюринга (или комбинаторной системы). С точностью до вариантов изложения мы можем теперь дать самое общее определение грамматики в терминах машин Тьюринга (или комбинаторных систем). Сказать, что грамматика G некоторого языка L, определенного над словарем V, есть перечисляющий алгоритм, — значит утверждать, что существует машина Тьюринга ZG, которая сопоставляет числу 1
фразу фь числу 2 — фразу ф2..... любому натуральному числу
п — фразу фи, так что производимое машиной Za рекурсивно перечислимое множество {фь ф2.....фп, ...} совпадает с L.
Этот алгоритм (или другой алгоритм, родственный ему) может быть представлен как «средство распознавания». Именно, машине предлагается фраза ф, и если эта фраза принадлежит языку — и только в этом случае, — машина должна остановиться после конечного числа операций. Таким образом: . если машина останавливается, ф принадлежит языку; .. если же машина не остановилась, мы ничего не можем сказать о принадлежности фразы ф языку.
Однако в классе всех рекурсивно перечислимых языков не существует распознающего алгоритма, который всегда давал бы от-
') Ср. примечание к стр. 66. — Прим. ред. Гл. VII. Контекстно-свободные языки
113
вет «да» или «нет» на вопрос о принадлежности любой фразы данному языку.
Классы грамматик. Крайняя общность только что приведенных определений не позволяет ухватить некоторые специфические особенности реально существующих языков (естественных и искусственных) и соответствующих грамматик. Поэтому данные понятия необходимо разумным образом сузить.
Налагая на грамматики дополнительные условия, мы можем получить иерархию классов грамматик, последовательно вложенных друг в друга. Разным классам грамматик отвечают более специфические (нежели машины Тьюринга) классы автоматов или комбинаторных систем.
Можно было бы определить все интересные классы грамматик сразу; однако, учитывая дидактические цели настоящей книги, мы предпочли начать с рассмотрения одного класса грамматик, занимающего в иерархии среднее положение. Этот класс естественным образом появляется при изучении синтаксиса; мы охарактеризуем его сперва эвристически.
7.1.2. Об одной весьма распространенной структуре
В качестве примеров мы будем брать французские фразы. Примем допущение, что мы всегда умеем установить, является ли данная последовательность французских слов фразой. При синтаксическом анализе будем опираться на понятия школьной грамматики.
Говоря о грамматике, мы будем пользоваться именами синтаксических категорий, такими, как «существительное», «глагол», «именная группа» и т. д. Ясно, что если слово существительное само является существительным, то слово глагол — не глагол; категория и обозначающее ее слово (или словосочетание) должны строго различаться.
