Математическая теория формальных языков
Гомоморфизмы и контекстно-свободные языки
Теорема 11.2.1.
Для любого гомоморфизма
и контекстно-свободного языка
язык h(L) является контекстно-свободным.
Доказательство. Приведем здесь доказательство, использующее МП-автоматы, хотя эту теорему легко доказать и с помощью контекстно-свободных грамматик. Пусть язык L распознается МП-автоматом . Тогда язык h(L) распознается МП-автоматом , где
Пример 11.2.2.
Пусть
и . Рассмотрим контекстно-свободный язык L, порождаемый грамматикой
и гомоморфизм , заданный равенствами h(a) = a, h(b) = bba и h(c) = a. Тогда язык h(L) порождается контекстно-свободной грамматикой
Упражнение 11.2.3. Пусть гомоморфизм
задан соотношениями h(a) = b, , h(c) = a. Рассмотрим язык L, порождаемый грамматикой
Найти контекстно-свободную грамматику для языка h(L).
Теорема 11.2.4.
Для любого гомоморфизма
и контекстно-свободного языка
язык h-1(L) является контекстно-свободным.
Доказательство. Введем обозначение
Пусть язык L распознается МП-автоматом . Без ограничения общности можно считать, что для каждого перехода
выполняется неравенство . Можно проверить, что в этом случае язык h-1(L) распознается МП-автоматом , где
Пример 11.2.5.
Пусть
и . Рассмотрим гомоморфизм , заданный равенствами h(c) = aa, h(d) = b и h(e) = bba. Пусть контекстно-свободный язык L распознается МП-автоматом , где Q = {p}, , I = {p}, F = {p},
Тогда язык h-1(L) распознается МП-автоматом , где , ,
и
Язык h-1(L) также порождается контекстно-свободной грамматикой
Упражнение 11.2.6. Пусть гомоморфизм
задан соотношениями h(a) = ab, h(b) = aaba, h(c) = b. Рассмотрим язык L, порождаемый грамматикой
Описать язык h-1(L).
Упражнение 11.2.7.
задан соотношениями h(c) = a, h(d) = ba, h(e) = bb. Рассмотрим язык L, порождаемый грамматикой
Найти контекстно-свободную грамматику для языка h-1(L).
Упражнение 11.2.8. Пусть гомоморфизм
задан соотношениями , , . Рассмотрим язык , порождаемый грамматикой
Найти контекстно-свободную грамматику для языка h-1(L).
Упражнение 11.2.9. Обозначим через L язык, порождаемый грамматикой
Рассмотрим гомоморфизм , заданный соотношениями
h1(a) = ac , h1(b) = bc , h1(c) = aa , h1(d) = ab , h1(e) = ba , h1(f) = bb ,
и гомоморфизм , заданный соотношениями
h2(a) = a , h2(b) = b , h2(c) = ab , h2(d) = aa , h2(e) = bb , h2(f) = ba .
Найти контекстно-свободную грамматику, порождающую язык
