Математическая теория формальных языков
Деление контекстно-свободных языков
Теорема 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}, что язык
не является контекстно-свободным?
