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




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

Упражнения

  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), встречается в ω-языке, соответствующем некоторому регулярному языку. Покажите также, что такой ω-язык обязательно содержит в качестве подслов ω-слова с произвольно высокими степенями xi. (По этой причине при решении проблемы Туэ DOL-системы оказываются гораздо удобнее конечных автоматов.)
  11. Исследуйте свойства замкнутости семейств регулярных, контекстно-свободных и рекурсивно перечислимых языков относительно булевых и регулярных операций (Общий обзор свойств замкнутости дается в [Sa2]****.) В частности, покажите, что пересечение двух контекстно-свободных языков не обязательно контекстно-свободно, в то время как пересечение контекстно-свободного языка с регулярным всегда является контекстно-свободным языком. (Указание. Последний факт устанавливается "конструкцией троек", которая часто оказывается очень полезной в теории языков: нетерминалами объявляются тройки (p, α, q), где α - символ данной грамматики, а p и q - вершины данного автомата. Эти тройки используются для моделирования как выводов в грамматике, так и переходов автомата. Например, продукции A→BC соответствует множество продукций (p, A, q) → (p, B, q1)(q1, C, q), где p и q - произвольные состояния автомата. Продукции (p, α, q) добавляются в том случае, когда в автомате есть стрелка, ведущая из p в q и помеченная буквой а. Множество начальных символов состоит из нетерминалов вида (q0, S, qF), где q0 - начальная вершина, qF - заключительная вершина, а S - начальный символ.)

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

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

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

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

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








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