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

Пример 9.3.1. Пусть . Язык является линейным, так как он порождается грамматикой

Пример 9.3.2. Рассмотрим алфавит . Язык

является линейным, так как он порождается грамматикой

Теорема 9.3.3. Если L₁ и L₂ - линейные языки над алфавитом , то тоже линейный язык.

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

где .

Пример 9.3.4. Рассмотрим алфавит . Язык

является линейным, поскольку

где языки

являются линейными, а язык

является автоматным, и можно применить теоремы 9.3.3, 3.2.1, 2.4.1 и лемму 1.5.13.

Упражнение 9.3.5. Пусть . Является ли линейным язык ?

Упражнение 9.3.6. Пусть . Является ли линейным язык ?

Упражнение 9.3.7. Найти линейную грамматику, порождающую язык , где L₁ порождается грамматикой

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

Теорема 9.4.1. Если L - контекстно-свободный язык, то L^* тоже контекстно-свободный язык.

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

где .

Теорема 9.4.2. Если L₁ и L₂ - контекстно-свободные языки над алфавитом , то тоже контекстно-свободный язык.

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

где .

Теорема 9.4.3. Если L₁ и L₂ - контекстно-свободные языки над алфавитом , то тоже контекстно-свободный язык.

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

где .

Теорема 9.4.4. Если L - контекстно-свободный язык, то тоже контекстно-свободный язык.

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

Упражнение 9.4.6. Найти контекстно-свободную грамматику для языка , где L₁ порождается грамматикой

а язык L₂ порождается грамматикой

Пересечение и дополнение контекстно-свободных языков

Теорема 9.5.1. Неверно, что для любых контекстно-свободных языков L₁ и L₂ язык тоже контекстно-свободный.

Доказательство. Положим и . В примере 9.2.1 было доказано, что язык не является контекстно-свободным.

Теорема 9.5.2. Неверно, что для любого контекстно-свободного языка язык тоже контекстно-свободный.

Доказательство. Положим , где . В примере 9.3.4 было доказано, что язык L является линейным (и следовательно, контекстно-свободным).

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

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

Упражнение 9.5.5. Существует ли такой линейный язык L над алфавитом {a,b}, что язык не является контекстно-свободным?