7.2. Плотная иерархия грамматических семейств

Среди грамматических семейств представляют значительный интерес лишь некоторые широко исследуемые семейства., такие, как семейства регулярных, линейных и контекстно-свободных языков. Однако в целом существует "очень много" грамматических семейств в силу замечательной порождающей способности морфизмов. Чтобы формально доказать это утверждение, начнем с некоторых определений.

Пусть и ' - такие грамматические семейства, что ⊆'. Пара (, ') называется плотной, если для любых грамматических семейств ₁ и ₂, таких, что

существует такое грамматическое семейство ₃, что ₁₃₂. (Было бы ошибкой считать семейства между и ' линейно-упорядоченными; в общем случае среди них будет много несравнимых семейств.)

Грамматическое семейство ₂ называется последователем грамматического семейства ₁ (а ₁ называется предшественником₂), если ₁₂ и не существует грамматического семейства ₃ со свойством ₁₃₂.

Рассмотрим в качестве примера грамматику G и натуральное число k≥1, не принадлежащее множеству длин языка L(G), (Определение множества длин дано в упр. 6.4.)

Пусть b₁, ..., b_k - новые различные терминальные символы, а G₁ - грамматика, получающаяся из G добавлением продукции

(Как обычно, S обозначает начальный символ.) Тогда легко проверить, что (G₁) является последователем 3'{G). Самое существенное здесь то, что все символы b различны и отличаются от терминальных символов грамматики G. Предполагается также, что символ S не входит в правые части продукций.

Например, если G определяется продукциями

то, повторяя указанное выше построение, мы получим бесконечную последовательность грамматических семейств, в которой каждое семейство, начиная со второго, является последователем предыдущего семейства (в смысле данного выше определения), а первым является (G).

Следовательно, если множество длин языка L(G') содержит в собственном смысле множество длин языка L(G), то пара ((G),(G')) не может быть плотной. С другой стороны, известно много плотных пар семейств, для которых множества длин, соответствующих порождающим их грамматикам, совпадают. Мы хотим показать, что семейства регулярных и контекстно-свободных языков образуют плотную пару.

В доказательстве теоремы важную роль играет приведенная ниже лемма. Прежде чем мы ее сформулируем, введем еще одно вспомогательное понятие. Язык L называется когерентным, если его нельзя представить в виде L = L₁∪L₂, где L₁ и L₂ - языки над непересекающимися алфавитами и как L₁, так и L₂ содержит хотя бы одно непустое слово. Таким образом, язык {ab, bc, dc) когерентен, тогда как язык {a, bc} не когерентен.

Лемма 7.7. Пусть ₁ и ₂ - такие грамматические семейства, что ₁₂ и, кроме того, существует бесконечный когерентный язык L, принадлежащий ₂\₁. Тогда существует грамматическое семейство ₃, такое, что

₁₃₂(7.6)

Доказательство. Обозначим через L_i (i = 1, 2, ...) подмножество языка L, состоящее из всех слов длины ≠i. Мы хотим показать, что для некоторого pL_p∉₁ и L_p≠L.

Поскольку язык L бесконечен, L_i≠L для бесконечного множества значений i. Предположим, что все такие L_i принадлежат семейству ₁ и что грамматика G₁ порождает семейство ₁, а H_i является порождающей язык L_i интерпретацией грамматики G₁. Для каждого i существует побуквенный морфизм h_i, отображающий H_i на подграмматику G₁. Так как терминальный алфавит каждой грамматики H_i содержится в алфавите языка L, то существуют два различных числа i и j, таких, что ограничения h_i и h_j на терминалы идентичны. (Это, очевидно, вытекает из того, что для любых алфавитов ∑ и Δ существует лишь конечное число побуквенных морфизмов h: ∑^*→Δ^*.)

Рассмотрим теперь языки L_i и L_j. Без потери общности можно предположить, что нетерминальные алфавиты грамматик H_i и H_j не пересекаются. Естественным образом определив объединение морфизмов и объединение грамматик, мы видим, что объединение h морфизмов h_i и h_j удовлетворяет соотношению

(Для этого заключения необходимо, чтобы h_i и h_j отображали терминалы одинаковым образом.) Но это означает, что язык L_i∪L_j = L принадлежит ₁, а это противоречит нашей гипотезе.

Следовательно, существует число p, такое, что L_p∉₁ и L_p≠L. Очевидно, что любое переименование нетерминальных и терминальных символов грамматики оставляет неизменным порождаемое ею семейство. В дальнейшем будем считать, что G₁ и H_p (грамматика для L_p) не содержат общих букв (в случае необходимости мы переименуем алфавиты грамматики G₁).

Рассмотрим объединение G₃ грамматик G₁ и H_p (таким образом, каждый элемент в G₃ является объединением соответствующих элементов в G₁ и H_p) и положим ₃ = (G₃). Мы утверждаем, что выполняется (7.6).

По определению G₃ семейство ₃ содержит ₁. Это включение является собственным, поскольку L_p≠₁, но, очевидно, L_p∈₃.

Так как L∈₂, то и L_p∈₂ (Это утверждение следует из результата, приведенного в упр. 6, но его можно проверить и непосредственно, модифицируя порождающую L грамматику таким образом, что все слова длины ≤p получаются непосредственно из начального символа; см. также второе утверждение леммы 7.3.) Следовательно, можно предположить, что H_p является интерпретацией грамматики G₂, порождающей семейство ₂. Согласно последнему утверждению леммы 7.1, семейство (H_p) является частью ₂.

Заметим теперь, что каждый язык из ₃ имеет вид K₁∪K₂, где K₁∈₁, K₂∈(H_p) и, кроме того, алфавиты языков K₁ и K₂ не пересекаются. Из того что оба семейства (H_p) и ₁ содержатся в ₂, следует, что и ₃ содержится в ₂. (Здесь непересечение алфавитов является весьма существенным; в противном случае сделанное заключение не обязательно справедливо.)

Теперь используем тот факт, что язык L когерентен. Из него следует, что язык L, принадлежащий ₃, должен содержаться в одной из частей ₃, т. е. либо в ₁, либо в (H_p). Первый вариант исключается по предположению, а второй в силу того (см. лемму 7.2), что ни один язык в (H_p) не содержит слов длины p. Так как L_p≠L, то язык L содержит хотя бы одно слово длины p.

Следовательно, язык L принадлежит разности ₂\₃, что завершает проверку (7.6).▫

Теорема 7.8. Грамматические семейства регулярных и контекстно-свободных языков образуют плотную пару.

Доказательство. Рассмотрим два произвольных грамматических семейства ₁ и ₂, ₁₂ лежащие между семействами регулярных и контекстно-свободных языков. Стало быть, в разности ₂\₁ содержится некоторый язык L. Так как ₁ содержит все регулярные, а значит, и все конечные языки, то язык L бесконечен. Чтобы стало возможным применение леммы 7.7, надо еще показать, что язык L когерентен. Конечно, это не обязательно имеет место для произвольного языка L из разности ₂\₁. Однако мы покажем, что каждый L содержит бесконечное когерентное подмножество U, принадлежащее разности ₂\₁.

Итак, пусть язык L не когерентен: L = L₁∪L₂, где L₁ и L₂ - языки над непересекающимися алфавитами (и каждый из языков L₁ и L₂ содержит хотя бы одно непустое слово). Оба языка L₁ и L₂ принадлежат ₂, потому что L лежит в ₂. (Это опять-таки следует либо из упр. 6, либо доказывается непосредственно, исходя из грамматики для L.) Если оба языка L₁ и L₂ принадлежат ₁, то язык L также должен принадлежать ₁, а это невозможно. Значит, один из языков, скажем L₁, не принадлежит ₁. Из этого следует бесконечность L₁ (так как ₁ содержит все конечные языки).

Таким образом, мы нашли бесконечный язык L₁, принадлежащий разности ₂\₁. Кроме того, язык L\ оказывается над меньшим алфавитом, чем L. Если язык L₁ не когерентен, то повторяется та же процедура. После конечного числа шагов мы найдем бесконечный когерентный язык L', принадлежащий разности ₂\₁. Далее применяется лемма 7.7.▫

Эффективность проведенного построения обсуждается в упр. 8.