НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

Упражнения

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

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

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru