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


           

Свойства замкнутости класса контекстно-свободных языков


Теорема 9.4.1.

Если L - контекстно-свободный язык, то L*

тоже контекстно-свободный язык.

Доказательство. Пусть язык L порождается контекстно-свободной грамматикой . Тогда язык L*

порождается грамматикой

где .

Теорема 9.4.2.

Если L1

и L2 - контекстно-свободные языки над алфавитом , то

тоже контекстно-свободный язык.

Доказательство. Пусть язык L1

порождается контекстно-свободной грамматикой

и L2

порождается контекстно-свободной грамматикой , где . Тогда

порождается грамматикой

где .

Теорема 9.4.3.

Если L1

и L2 - контекстно-свободные языки над алфавитом , то

тоже контекстно-свободный язык.

Доказательство. Пусть язык L1

порождается контекстно-свободной грамматикой

и L2

порождается контекстно-свободной грамматикой , где . Тогда

порождается грамматикой

где .

Теорема 9.4.4.

Если L - контекстно-свободный язык, то

тоже контекстно-свободный язык.

Упражнение 9.4.5. Является ли контекстно-свободным язык ?

Упражнение 9.4.6.

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

порождается грамматикой

а язык L2

порождается грамматикой



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





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий