Математическая теория формальных языков
Представления контекстно-свободных языков посредством гомоморфизмов
Теорема 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, порождаемый грамматикой
Найти такой гомоморфизм , что
