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

Пример 9.3.1.

Пусть . Язык

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

Пример 9.3.2.

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

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

Теорема 9.3.3.

Если L1

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

тоже линейный язык.

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

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

и L2

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

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

где .

Пример 9.3.4.

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

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

где языки

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

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

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

Пусть . Является ли линейным язык ?

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

Пусть . Является ли линейным язык ?

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

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