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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



Пример 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 порождается грамматикой

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

Теорема 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 порождается грамматикой

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

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

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

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

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

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

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

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



Последнее изменение этой страницы: 2021-04-04; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.236.16.13 (0.024 с.)