Упражнения

1. Семейство 3 языков называется полным абстрактным семейством языков (АСЯ)^*, если оно замкнуто относительно каждой из следующих операций: объединение, ^*(итерация), морфизм, инверсный морфизм и пересечение с регулярными языками. Докажите, что каждое полное АСЯ замкнуто также относительно катенации и конечной подстановки.
2. Докажите, что семейства регулярных, контекстно-свободных и рекурсивно перечислимых языков являются полными АСЯ. (Наше соглашение - ограничить рассмотрение только А-свободными языками - здесь не применимо.) Докажите, что, с другой стороны, семейства DOL- и OL-языков являются "антиАСЯ", т. е. не замкнуты относительно ни одной АСЯ-операции. (Исчерпывающее изложение теории АСЯ читатель может найти в [G2]^**.)
3. Объясните, почему в формуле (7.2) фигурирует G₁', а не G₁ (Например, рассмотрите грамматику H₁, заданную продукцией S→ab, грамматику H₂, заданную продукциями S→ab, S→cd, и грамматику H₃, заданную продукциями S→ab, S→ba. Какие следствия имела бы замена G₁' на G₁ в формуле (7.2)? Осталась бы верной лемма 7.3?)
4. Сформулируйте и докажите соответствующий теореме 7.6 результат для семейства, всех регулярных языков (вместо рассмотренных в тексте Я-свободных).
5. Рассмотрим семейство линейных языков, т. е. языков, порождаемых линейными грамматиками. Докажите результаты о линейной достаточности и линейной полноте, соответствующие лемме 7.5 и теореме 7.6. Эта теория значительно сложнее аналогичной теории для регулярных языков. При желании читатель может найти информацию в [MSW2].
6. Обобщая рассуждения, использованные в доказательстве леммы 7.5, * покажите, что каждое грамматическое семейство замкнуто относительно пересечения с регулярными языками, Иначе говоря, если L - язык из этого семейства, a R - регулярный язык, то L∩R принадлежит семейству. Покажите также, что семейство языков, порожденное грамматикой только с одним терминальным символом, замкнуто относительно объединения. Зачем необходимо предположение об единственном терминале?
7. Грамматическое семейство называется унарно-полным, если для любой грамматики G, удовлетворяющей условию = , существует a-ограничение G_a, удовлетворяющее условию (G_a) = . Исследуйте понятие унарной полноты. (Теорема 7.6 показывает, что семейство регулярных языков унарно-полно. То же самое справедливо для линейных языков, см. упр. 5. Можно показать также, что семейство контекстно-свободных языков унарно-полно.)
8. Покажите, что конструкция в доказательстве теоремы 7.8 эффективна в следующем смысле. Предположим, известно, что ₁₂ и дан язык L, принадлежащий разности ₂\₁. Тогда можно эффективно построить грамматическое семейство ₃, удовлетворяющее условию ₁₃₂. (Проблема равенства грамматических семейств, т. е. проблема -выяснения, верно ли, что (G₁) = (G₂) в случае двух произвольно выбранных контекстно-свободных грамматик G1 и G₂, остается открытой^***.)
9. Покажите, что между любыми двумя семействами в иерархии (7.7) найдется некоторое цветосемейство. (Рассмотрите нечетное число "склеенных" вместе циклов.)
10. Покажите, что семейство орграфов, ассоциированное с языком L = {ab, bc}, является последователем семейства орграфов, ассоциированного с языком {ab}. (Понятие последователя определяется здесь точно так же, как для цветосемейетв.) Покажите, что семейство орграфов, ассоциированное с L₃ = {ab, bc, cd}, не является, однако, последователем семейства орграфов, ассоциированного с L₂. Покажите, что семейство орграфов, ассоциированное с языком {ab, bc₁, b₁c₁, b₁c, cd}, является предшественником семейства, ассоциированного с L₃. (См. в [MSW4] обсуждение соответствующих иерархий. Не известен ни один пример последователя, если орграфы более сложны, например содержат циклы.)
11. Заметим, что каждый граф (соответственно орграф) является интерпретацией графа (соответственно, орграфа), содержащего петлю. Это основная причина того, почему такие графы и орграфы были исключены из рассмотрения. Покажите, что семейство орграфов, ассоциированное с языком {a²}, не имеет предшественника.
12. Сопоставьте каждой контекстно-свободной грамматике некоторый конечный язык. Рассмотрите интерпретации такого языка наряду с интерпретациями исходной грамматики. Постройте коммутативную диаграмму, а также исследуйте ее отношение к семейству языков, порождаемых всеми интерпретациями исходной грамматики.
13. Покажите, что цветосемейства образуют плотное частично упорядоченное множество, т. е. что между двумя любыми цветосемействами, одно из которых строго содержится в другом, существует строго промежуточное цветосемейство. Указания. Сначала рассмотрите произвольный циклический граф вида C_2m+1. Покажите, что существуют произвольно большие связные графы H, такие, что (i) H является интерпретацией графа C_2m+1, но не обратно и (ii) если отождествить две любые несмежные зершины в H, то C_2m+1 окажется интерпретацией полученного графа. Заключите отсюда, что не существует графа, для которого граф C_2m+1 был 5ы последователем. Распространите это заключение на произвольный связный граф G, в который C_2m+1 входит как наименьший нечетный цикл, посредством "замещения" одного вхождения этого цикла графом H. После этого заключение легко распространить и на случай несвязных графов. (Это упражнение основано на частном сообщении Э. Велцля.)

^* (В отечественной литературе такие семейства иногда называют полными многообразиями (см. также замечание 3° на с. 137).- Прим. перев.)

^** (На русском языке имеется изложение теории АСЯ в ряде статей в сборнике [ЯиА*].- Прим. перев.)

^*** (Относительно этого упражнения см. замечание 1° переводчика в конце главы.- Прим. ред.)

Замечания переводчика 1°. Алгоритмы для проблемы включения, а следовательно, и проблемы равенства грамматических семейств (г. с.) изложены в работе [GGoSp*]. Сначала выделяются три тривиальные г. c.: L_∅ = {∅}, где ∅ - пустой язык, L_λ = {∅, {λ}}, L_tin = {L|L конечен}. В более ранней работе [CrGSp*] были предложены алгоритмы для решения проблем, порождает ли произвольно выбранная контекстно-свободная грамматика (КСГ) G г. с.: L_∅, L_λ, L_tin и L_CF - семейство всех контекстно-свободных языков (в последнем случае Саломаа называет КСГ G полной). Г. с. называется собственным, если оно нетривиально и является собственной частью семейства LCF. Полным полуАСЯ называется семейство языков, содержащее непустой язык и замкнутое относительно морфизма, инверсного морфизма, пересечения с регулярными множествами и объединения. Для любого множества языков через φ() и F() обозначаются соответственно наименьшее полное полуАСЯ и наименьшее полное АСЯ, содержащее . Полное полуАСЯ называется главным, если существует язык L, такой, что = φ ({L}). В работе [CrG] доказан важный результат о том, что каждое нетривиальное г. с. является полным главным полуАСЯ. Алгоритм для решения проблемы включения г. с. в [GGoSp*] основан на методе разложения г. с. Определяются сумма г. с.

и их произведение

Выражение вида

называется многочленом г. с. (sum-of-products). Если удаление из многочлена любого _ij приводит к многочлену, обозначающему строго меньшее Г. с, то многочлен называется минимальным. Г. с. называется простым (аддитивно простым), если для любых г. с. ₁ и ₂ из (соответственно ) следует или . Доказывается, что г. с. аддитивно просто тогда и только тогда, когда оно является конечным произведением нескольких простых г. с. Основным результатом является замечательная теорема простого разложения: каждое г. с. единственным образом (с точностью до переименования) представимо в виде минимального многочлена от простых г. с, причем этот многочлен можно эффективно найти по заданию исходного г. с. порождающей его грамматической формой. С помощью этой теоремы проблема включения г. с. сводится к частному случаю, когда первое г. с. просто, а второе является произведением простых. Для дальнейшего решения вводится еще одна операция над г. е. Грамматика G = (V, ∑, P, σ) называется сплит-линейной (split linear), если правая часть каждой продукции в G принадлежит множеству

где A, B, C образуют разбиение ∑. Для г. с. ₁, ₂₃ через (₁, ₂₃) обозначается семейство языков вида τ(L), где L = L(G) для некоторой сплит-линейной грамматики

а τ — такая подстановка на (A∪C∪B)^*, что τ(x) принадлежит ₁, ₂₃, если x принадлежит A, C или B соответственно. Собственное г. с. является простым тогда и только тогда, когда оно имеет одну из альтернативных форм или Семейство регулярных языков играет роль единицы относительно Оказывается, что любое г. с. строится из с помощью операций и , причем его представление находится эффективно. Существует единственное каноническое представление, уточняющее представление в виде минимального многочлена. Два нетривиальных г. с. равны тогда и только тогда, когда совпадают их канонические представления. Включение г. с. также выводится из их канонических представлений. Каноническое представление дает большую информацию о структуре г. с., и, вероятно, с его помощью можно получить решение многих проблем, связанных с г. с. Было бы интересно распространить введенные понятия на произвольные полные полуАСЯ.

2°. Различные модификации схем грамматик, позволившие получить kC содержательные результаты, относящиеся к семействам языков, отличных от , а также к субрегулярным семействам, рассматриваются в работах [W], [MPSW*] и [OSW*].

3°. Естественно определяемые классы сложности языков обычно являются АСЯ, хотя и не полными (см. [АиЯ*] и замечание в конце гл. 6). Таким образом, контекстные языки образуют (просто) АСЯ и распознаются недетерминированными машинами Тьюринга с линейной памятью. Среди классов временной сложности аналогичную роль играет абстрактное семейство языков квазиреального времени (см. [Bea*]).