Математическая теория формальных языков
Свойства замкнутости класса автоматных языков
Теорема 3.1.1. Класс автоматных языков замкнут относительно итерации, конкатенации и объединения.
Доказательство. Без ограничения общности можно предположить, что каждый из исходных языков задан конечным автоматом с одним начальным и одним заключительным состоянием. Тогда во всех трех случаях результирующий автомат получается из исходных путем добавления нескольких -переходов и состояний и назначения новых начальных и заключительных состояний.
Пример 3.1.2. Пусть . Рассмотрим конечный автомат
где
Тогда язык L(M1)*
распознается конечным автоматом
Пример 3.1.3.
Пусть . Рассмотрим конечный автомат M1
из примера 3.1.2 и конечный автомат
где
Тогда язык
распознается конечным автоматом
а язык
распознается конечным автоматом
Упражнение 3.1.4.
Существует ли такой автоматный язык L, что язык LR
не является автоматным?
Упражнение 3.1.5.
Существует ли такой автоматный язык , что язык Pref(L) не является автоматным?
Упражнение 3.1.6.
Существует ли такой автоматный язык , что язык Suf(L) не является автоматным?
Упражнение 3.1.7.
Существует ли такой автоматный язык , что язык Subw(L) не является автоматным?
Упражнение 3.1.8.
Существует ли такой автоматный язык , что язык Subseq(L) не является автоматным?
Упражнение 3.1.9.
Существует ли такой автоматный язык L, что язык
не является автоматным?
Упражнение 3.1.10. Существует ли такой автоматный язык L, что язык
не является автоматным?
Упражнение 3.1.11. Найти праволинейную грамматику, порождающую язык
Упражнение 3.1.12. Найти праволинейную грамматику, порождающую язык L*, если язык L порождается грамматикой
