Математическая теория формальных языков



             

Деление контекстно-свободных языков


Теорема 11.1.1.

Пусть L1 - контекстно-свободный язык над алфавитом

и L2 - автоматный язык над алфавитом . Тогда язык

является контекстно-свободным.

Доказательство. Пусть - МП-автомат, распознающий язык L1. Без ограничения общности можно считать, что для каждого перехода

выполняется неравенство .

Пусть - конечный автомат, распознающий язык L2. Без ограничения общности можно считать, что

и для каждого перехода

выполняется равенство |x| = 1.

Тогда язык

распознается МП-автоматом , где , I = I1,

и

Пример 11.1.2.

Пусть , язык L1

распознается МП-автоматом

и язык L2

распознается конечным автоматом

Следуя доказательству теоремы 11.1.1, получаем, что язык

распознается МП-автоматом, изображенным ниже.

Пример 11.1.3.

Пусть ,

и . Тогда

Пример 11.1.4.

Пусть ,

и . Тогда

Замечание 11.1.5.

Пусть

и . Язык

является контекстно-свободным тогда и только тогда, когда язык L является контекстно-свободным.

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

Существует ли такой контекстно-свободный язык , что язык Subw не является контекстно-свободным?

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

не является контекстно-свободным?

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

не является контекстно-свободным?




Содержание  Назад  Вперед