Математическая теория формальных языков



             

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


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

Найти контекстно-свободную грамматику, порождающую язык




Содержание  Назад  Вперед