Гомоморфизмы и контекстно-свободные языки

Теорема 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},