Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
S-^giShi, !<*'<« Гл. VIII. Нераспознаваемые свойства КС-грамматик
131
где gi и hi — непустые цепочки в алфавите {а, Ь).
Язык Ln содержит цепочку 'с'\ именно поэтому мы изменили язык Lm так, чтобы он не содержал этой цепочки — иначе пересечение этих двух языков всегда было бы непусто.
Вопрос о том, пусто ли пересечение языков Lm и Lni равносилен вопросу, содержит ли Ln симметричную цепочку МсЯ. Иначе говоря, он равносилен вопросу о существовании последовательности индексов
'ь h> ¦ • • > lkt
такой, что цепочка
StlSii ¦¦-Sik
есть обращение цепочки
Aia... Ai2 Ai1 ¦
В конечном счете нужно выяснить, существует ли такая последовательность индексов ii, iz, ..., 'л, что SilSi1 ¦ • • Sik совпадает с Hll Hlj... hik.
Нетрудно узнать в этой задаче проблему Поста для пар
(gi, A1), ..., (Sn, А„);
следовательно, поставленная нами проблема неразрешима.
Поскольку проблема (1) неразрешима для данного частного случая (а именно, для пар с фиксированным первым элементом Gm и вторым элементом вида Gn, зависящим от выбора цепочек gi. •••> Sh, Аь ..., Aft), она неразрешима и в общем случае.
8.1.2. Проблема автоматности пересечения
Если пересечение определенных выше языков Lm и Ln содержит цепочку
SilSi2 • • • SikChtk ... Ai2Aii = XCX
(соответствующую решению проблемы Поста), то оно содержит также для любого п цепочку
(ShSi2---SikTcttik... Ai2Aii)".
Таким образом, пересечение двух КС-языков оказывается бесконечным подмножеством языка Lm. Однако ни одно бесконечное подмножество этого языка не может быть А-языком (это легко показать, используя один из основных фактов теории А-языков, который будет установлен ниже, а именно следствие из теоремы П- 14.3.5). В то же время пустой язык, очевидно, является автоматным. Итак, пересечение L'm[\Ln является А-языком тогда и только тогда, когда оно пусто. Но проблема пустоты пересечения ^m П Ln неразрешима; следовательно4 неразрешима и проблема его 132
Часть II. Некоторые замечательные классы языков
автоматности. Тем более неразрешима проблема автоматности пересечения двух КС-языков в общем случае. Таким образом, мы можем сформулировать следующую теорему.
Теорема. Не существует алгоритмов, позволяющих установить-. а) является ли пересечение двух КС-языков непустым; б) является ли пересечение двух КС-языков А-языком.
Эта теорема остается справедливой даже для такого специального случая, как пересечение двух минимальных линейных языков, один из которых фиксирован.
8.1.3. Проблема «контекстной свободности» пересечения
С помощью аналогичной техники, используя вместо Lfm язык {хсхсусу}, з вместо Lji — язык, порождаемый грамматикой S-*aSa S-*bSb S-*acTca
S-*bcTcb '
T-^giThi, 1 <г<» T-* с
и замечая, что никакой бесконечный подъязык языка {хсхсхсх} не является КС-языком (это устанавливается рассуждениями, сходными с теми, которые были применены в п. 7.2.5), можно доказать следующую теорему:
Теорема. Не существует алгоритма, позволяющего установить, является ли пересечение двух КС-языков КС-языком.
8.1.4. Дополнение
Нетрудно было бы показать (непосредственным_ построением соответствующих грамматик),
что дополнения Lm и Ln языков Lm и Ln являются КС-языками. Поэтому Lm U Ln — также КС-язык. Но Lm U Ln = Lm П Ln, а мы доказали, что проблемы распознавания пустоты, конечности и автоматности пересечения Lm Г) Ln неразрешимы; таким образом, не существует алгоритмов, распознающих пустоту, конечность или автоматность дополнения к Lm U Ln- То же рассуждение можно применить к языкам, использованным в п. 8.1.3. Все это позволяет сформулировать следующую теорему:
Теорема. Свойства дополнения КС-языка быть пустым, конечным, А-языком и КС-языком нераспознаваемы.
Эквивалентность. Из только что сформулированной теоремы следует, что не существует алгоритма, позволяющего устанавливать эквивалентность двух произвольных КС-грамматик Oi Гл. VIII. Нераспознаваемые свойства КС-грамматик
133
и U2- В самом деле, если бы такой алгоритм существовал, он позволял бы для произвольной КС-грамматики G отвечать на вопрос, верно ли, что L(G) = Vt, а это равносильно ответу на вопрос, является ли L(G) пустым.
Точно так же неразрешима проблема включения, т. е. не существует алгоритма, который для двух КС-языков Li и L2 отвечал бы «да» или «нет» на вопрос: верно ли, что Lі с L2 (действительно, такой алгоритм отвечал бы и на вопрос: верно ли, что VjcL(G)1 т. е. пусто ли L(G))?
§ 8.2. ПРОБЛЕМЫ, СВЯЗАННЫЕ С НЕОДНОЗНАЧНОСТЬЮ
В первом параграфе предыдущей главы мы показали, как можно описать структуру фразы с помощью дерева. КС-грамматики предназначаются для формализации именно этого способа представления синтаксической структуры. Правила вида А—*ср, где в левой части заменяется ровно один символ, позволяют представить любой вывод либо в виде дерева с помеченными узлами, либо с помощью помеченных скобок. Правда, в таком представлении не отражается порядок выполнения подстановок, однако он не имеет существенного значения.
8.2.1. Деревья вывода
