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

Пример 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₂ порождается контекстно-свободной грамматикой , где . Тогда порождается грамматикой