Упражнения

1. Покажите, что каждый конечный язык представим. (Выведите это из определения представимости; это утверждение, конечно, непосредственно следует из теоремы Клини.)
2. Назовем весом регулярного языка L и обозначим weight (L) наименьшее число вершин в конечном детерминированном автомате, представляющем I. Постройте алгоритм для нахождения weight (L), а также соответствующего минимального автомата. Покажите, что последний является единственным с точностью до изоморфизма. (Тривиальный, но практически неэффективный алгоритм состоит в систематическом переборе всех автоматов с весом, меньшим веса данного, и применении теоремы 2.8. Более эффективный алгоритм можно найти, например, в [Sal]^*)
3. Назовем представляющим числом регулярного языка L и обозначим repr (L) наименьшее возможное число заключительных вершин в конечном детерминированном автомате, представляющем L. Покажите на примерах, что repr (L) может быть произвольно большим. Исследуйте алгоритмы нахождения weight (L) и repr (L) для конечного языка L (см. [Sal]).
4. Покажите, что регулярный язык, представимый конечным детерминированным автоматом с n вершинами, бесконечен тогда и только тогда, когда он содержит такое слово w, что n≤|w|<2π. Докажите также "лемму о накачке", утверждающую, что каждое достаточно длинное слово w в регулярном языке L может быть записано в виде w = tuv, где u≠λ и tu'v∈L для всех i = 0, 1, 2, ... .
5. Пусть L - любой язык над алфавитом [a]. Докажите, что язык L* регулярен.
6. Рассмотрите произведение (2.2), сомножители которого определены таким же образом, как в доказательстве леммы 2.1. Покажите, что это произведение равно числу различных помеченных словом w путей из начальных вершин в заключительные.
7. Пусть L - язык над алфавитом ∑. Язык L индуцирует отношение эквивалентности ≡ _L на множестве ∑*, задаваемое условием: u ≡ _Lv имеет место тогда и только тогда, когда не существует слова w, такого, что только одно из слов uw и vw принадлежит L. Покажите, что язык L регулярен тогда и только тогда, когда индекс (т. е. число классов эквивалентности) отношения ≡ _L с конечен. Покажите также, что индекс ≡ _L равен weight (L). (Имеется весьма обширная литература, касающаяся отношения ≡ _L. Дополнительная информация о нем содержится, в частности, в [Ei], [Sal] и [Sa2]^**.)
8. Рассмотрим равенство α = β регулярных выражений α и β, означающее, что α и β задают один и тот же язык. Существует большое количество верных равенств, причем некоторые из них описывают простые свойства объединения и катенации, а другие выражают более тонкие соотношения между катенативным замыканием и прочими операциями. Например, верны следующие равенства, в которых α, β и γ - произвольные регулярные выражения:
   α∪(β∪γ) = (α∪β)∪γ, α(βγ) = (αβ)γ, α∪β = β∪α, α(β∪γ) = αβ∪αγ (α∪β)γ = αγ∪βγ ∅^*α, = α, ∅α = ∅, α^* = α^*α∪∅^*, α^* = (α∪∅^*)^*.
   Из приведенных выше равенств можно получить новые верные равенства посредством одновременной подстановки регулярных выражений вместо букв и следующего правила вывода: из равенства α = αβ∪γ следует равенство α = γβ^* при условии, что язык, заданный β, не содержит пустого слова. Покажите, что все верные равенства получаются таким способом (см. [Sal] и [Sa2], а также [MiS], где получено обобщение этого результата).
9. Исследуйте ω-языки, соответствующие конечным детерминированным автоматам. Подробнее обобщим понятие, введенное в упр. 1.14, следующим образом. Для каждого языка L соответствующий ω-язык состоит из ω-слов α, таких, что L содержит бесконечно много префиксов ω-слова α. Что можно сказать об ω-языках, соответствующих регулярным языкам? (Более подробные сведения можно найти в [Ei]^***.)
10. Покажите, что каждое из ω-слов, рассмотренных в связи с проблемой Туэ (теоремы 1.5 и 1.8, лемма 1.6), встречается в ω-языке, соответствующем некоторому регулярному языку. Покажите также, что такой ω-язык обязательно содержит в качестве подслов ω-слова с произвольно высокими степенями xⁱ. (По этой причине при решении проблемы Туэ DOL-системы оказываются гораздо удобнее конечных автоматов.)
11. Исследуйте свойства замкнутости семейств регулярных, контекстно-свободных и рекурсивно перечислимых языков относительно булевых и регулярных операций (Общий обзор свойств замкнутости дается в [Sa2]^****.) В частности, покажите, что пересечение двух контекстно-свободных языков не обязательно контекстно-свободно, в то время как пересечение контекстно-свободного языка с регулярным всегда является контекстно-свободным языком. (Указание. Последний факт устанавливается "конструкцией троек", которая часто оказывается очень полезной в теории языков: нетерминалами объявляются тройки (p, α, q), где α - символ данной грамматики, а p и q - вершины данного автомата. Эти тройки используются для моделирования как выводов в грамматике, так и переходов автомата. Например, продукции A→BC соответствует множество продукций (p, A, q) → (p, B, q₁)(q₁, C, q), где p и q - произвольные состояния автомата. Продукции (p, α, q) добавляются в том случае, когда в автомате есть стрелка, ведущая из p в q и помеченная буквой а. Множество начальных символов состоит из нетерминалов вида (q₀, S, q_F), где q₀ - начальная вершина, q_F - заключительная вершина, а S - начальный символ.)

^* (Вопросы эквивалентности состояний автоматов и минимизации подробно и глубоко разбираются в основополагающей статье Э. Ф. Мура [М*]. См. также [AHU], с. 165-168 и 354-366 перевода, и [ТрБ*].- Прим. перев.)

^** (Отношение ≡ _L было введено и изучалось Рабином и Скоттом; см. [PC*], а также [La].- Прим, перев.)

^*** (В отечественной литературе эта тема освещена в книге [ТрБ*].- Прим. перев.)

^**** (См. также [ЯиА*].- Прим. перев.)