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

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

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