Теорема 11.3.1. Рассмотрим алфавит и язык , порождаемый контекстно-свободной грамматикой G0:
Произвольный язык является контекстно-свободным тогда и только тогда, когда существует такой гомоморфизм , что L = h-1(L0) или .
Доказательство. Достаточность следует из теоремы 11.2.4. Приведем теперь идею доказательства необходимости (полное доказательство можно найти в [Сал, с. 103-109]).
Пусть дан произвольный контекстно-свободный язык L. Согласно теореме 8.4.6 язык порождается некоторой контекстно-свободной грамматикой , в которой каждое правило имеет один из следующих трех видов: , , , где .
Определим вспомогательную функцию , ставящую в соответствие каждому символу из конечный язык над алфавитом следующим образом:
Искомый гомоморфизм h определяется следующим образом: если
положим
Пример 11.3.2. Пусть . Рассмотрим язык L, порождаемый грамматикой
Тогда L = h-1(L0), где гомоморфизм h задан равенствами
h(d) = cb1b2b1a1a2a2a1a1a2a1c,h(f) = cb1b2b1cb1b2b2b1a1a2a2a2a1cb1b2b2b1a1a2a2a2a1a1a2a2a1c,h(g) = cb1b2b2b2b1c.Рассмотрим, например, слово . Проверим, что слово h(dffg) выводится в грамматике G0 из теоремы 11.3.1. Очевидно, что . С помощью последних пяти правил грамматики G0 можно вывести, что
|
|
Осталось найти такие шесть выводимых из C слов , что
Подходят слова
w1 = c,w2 = c,w3 = cb1b2b2b1a1a2a2a2a1cb1b2b2b1a1a2a2a2a1a1a2a2a1c,w4 = cb1b2b1c,w5 = cb1b2b2b1a1a2a2a2a1a1a2a2a1c,w6 = c.Теорема 11.3.3 (Теорема Хомского-Шютценберже). Язык является контекстно-свободным тогда и только тогда, когда существуют такие натуральное число n, автоматный язык L1 над алфавитом и гомоморфизм , что , где - язык Дика над 2n буквами.
Доказательство можно найти в [Лал, с. 331-333].
Упражнение 11.3.4. Рассмотрим язык L1, порождаемый грамматикой
и язык L2, порождаемый грамматикой
Найти такой гомоморфизм , что
К сожалению, теорема о детерминизации не переносится с конечных автоматов на автоматы с магазинной памятью. Возникает важный для практических приложений класс языков, распознаваемых детерминированными автоматами с магазинной памятью (то есть такими автоматами с магазинной памятью, которые ни в какой конфигурации не могут выбирать между несколькими очередными тактами). Точные определения этого класса автоматов и соответствующего класса языков даны в разделе 12.1. Чтобы получить полезный и естественный с точки зрения практики класс, нужно добавить в конец каждого слова специальный символ, называемый маркером конца слова. Языки из выделенного таким образом класса называются детерминированными контекстно-свободными языками. Во втором разделе лекции формулируется ряд свойств этого класса языков. Важность детерминированных контекстно-свободных языков для теоретической информатики обусловлена тем, что для каждого такого языка можно указать быстрый алгоритм, распознающий принадлежность слова этому языку.
|
|