Упражнения

1. Обобщенное регулярное выражение помимо обычных операций может содержать также операции пересечения и дополнения. Этим обобщенные регулярные выражения отличаются от регулярных выражений, определенных в гл. 2. Покажите, что язык L, заданный регулярным выражением (ababa)^*, может быть задан также звездно-свободным (или безытерационным) обобщенным регулярным выражением, т. е. L получается из языков ∅, {a), {b} конечным числом применений катенации и булевых операций. (Языки, задаваемые звездно-свободными обобщенными регулярными выражениями, совпадают с несчитающими языками; см. [McP].) По определению регулярный язык L является несчитающим, если существует такое натуральное n, что для всех слов x, y, z слово xyⁿz∈L тогда и только тогда, когда xyⁿ⁺¹z∈L. Например, язык {ab, ba}^* является несчитающим, а язык {a²}^* таковым не является¹. Заметим, наконец, что понятие звездной высоты естественным образом распространяется на обобщенные регулярные выражения. Не известно, будут ли при таком обобощении существовать языки со звездной высотой, большей 1.
2. Сокращением слова w мы называем любое слово, полученное из w удалением некоторых вхождений букв (возможно, всех или ни одного). Множество всех сокращений слов из языка L обозначим через abbr (L). Докажите, что из регулярности L следует регулярность abbr (L); при этом обратное утверждение неверно.
3. Покажите, что каждый бесконечный регулярный язык L, такой, что L⊆{a}^* и λ∈L, обладает СКС.
4. Конечный детерминированный автомат называется перестановочным автоматом, если в нем не существует двух различных вершин q₁ и q₂, таких, что из q₁ и q₂ в одну и ту же вершину q₃ ведут стрелки, помеченные одной и той же буквой a. Докажите непосредственно, что язык, представимый перестановочным автоматом и содержащий пустое слово, обладает СКС. Выразите верхнюю оценку для порядка языка через число вершин-автомата (см. [Li1]).
5. Язык L называется звездным языком, если L = L^*₁ для некоторого языка L₁; при этом L₁ называется корнем (из) языка L. Корень из L называется минимальным, если он содержится в каждом корне из L. Покажите, что если непустой регулярный язык L₁ является минимальным корнем, то L₁∪{λ} не обладает СКС (см. [Li1]).
6. Пусть α, β и γ - такие слова, что αβ'γ принадлежит R^* для любого i≥0. Покажите, что найдутся такие натуральные числа m, n и p, что слова x = αβ^m, y = βⁿ, z = β^pγ удовлетворяют (3.19).
7. Сформулируйте и докажите обращение леммы 3.10, используя при этом доказательство теоремы 3.15.

¹ (Несчитающие языки образуют важный подкласс класса регулярных языков (см. примечание).- Прим. перев.)