Глава 1

НЕКОТОРЫЕ ХАРАКТЕРИЗАЦИИ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ

В данной главе рассматриваются новые характеризации бесконтекстных языков. Каждой из них посвящен отдельный параграф. Порядок параграфов отражает логическую обусловленность одних характеризаций другими; он отвечает и хронологии их появления.

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

Dграфы - это представление бесконтекстных языков, которое, с одной стороны, естественным образом обобщает представление регулярных языков диа граммами состояний (подразумеваются состояния конечного автомата), с другой, может рассматриваться как промежуточное звено между магазинными автомата ми и морфическими представлениями, введенными Хомским и Шютценберже.

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

Оба тезиса достаточно выразительно иллюстрируются в настоящей работе. В параграфе 3, например, так называемое праволинейное разложение маршрута D -графа эксплуатирует идею общности между маршрутом протяжения 1 и дугой конечного автомата; КСвыражение, производимое по Dграфу, получается применением морфизма к КСвыражению, задающему успешные маршруты Dграфа. Основная теорема параграфа 2 обобщает известную теорему о морфическом пред -ставлении регулярных языков и т.д.

Параграф 2 содержит получаемую с помощью понятия D графа новую теорему о морфическом представлении бесконтекстного языка, из которой легко выводится теорема Хомского Шютценберже.

В параграфе 3 рассматривается понятие КС выражения. Оно появилось в ре зультате исследований по выявлению и адекватному выражению общей сути та ких формализмов, как магазинные автоматы, D графы, бесконтекстные грамма тики и морфические представления бесконтекстных языков. По существу, это ко нечное множество цепочек языка, определенным образом размеченных. Разметка указывает места разрастания цепочек и повторяемые при разрастании фрагмен ты. Одно только сопоставление определения КС выражения с широко известными очень полезными теоремами о разрастании цепочек бесконтекстного языка поз воляет надеяться на полезность нового понятия.

В данной работе понятие КС выражения послужило для открытия новых ха рактеризаций регулярных языков, по видимому, наименее ограничительных среди известных. Последний результат важен, если, например, считать жизнеспособны ми технологии вроде представленной в докторской диссертации [Мартыненко 98].

КСвыражения можно считать обобщением регулярных выражений, а теорема об их эквивалентности Dграфам является аналогом теоремы Клини.

Отметим, что попытки определить аналог регулярных выражений для задания бесконтекстных языков предпринимались давно. Например, Й. Груска [Gruska 71] ввел "характеристику"бесконтекстных языков с использованием объединения, конкатенации и "операционносимвольной итерации". Он был вынужден использовать "вспомогательные символы"(ср. наш алфавит именованных скобок). Их роль и количество имеют некоторое сходство с таковыми для пар соответствующих именованных скобок. Применил введенную характеристику для определения новых характеристик полулинейных языков и их подклассов.

В определении нашего КСвыражения и его применении явно и систематически используется оригинальное понятие D языка. На наш взгляд, понятие КС выражения является наиболее подходящим воплощением идеи согласованной под становки, обозначенной еще в 1966-1967 гг.

§1. Эграфы

Понятие D графа навеяно понятиями конечного и магазинного автоматов и воплощает наше стремление разработать в определенном отношении удачное гра фическое представление бесконтекстного языка. Оно тесно связано с понятием D языка, которое определяется и до некоторой степени изучается в разделе 1.1.

Dязыки обобщают известные языки Дика, точнее, ограниченные языки Дика. Dязыки, подобно языкам Дика, можно интерпретировать как множества скобочных систем, но взаимно однозначное соответствие открывающих скобок за крывающим теперь не обязательно. Таким образом, Dязык может использовать, например, меньше открывающих скобок, чем закрывающих.

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

Вычисления магазинного автомата после его нормализации по способу, пред ставленному в разделе 1.2, становятся фрагментами цепочек определенного D -языка. Это обуславливает полезность введенных в разделе 1.1 понятий для теории магазинных автоматов.

В разделах 1.2-1.3 рассматривается характеризация бесконтекстных языков D -графами. Раздел 1.2 содержит определение Dграфа и алгоритмы, которые преобразуют магазинный автомат в эквивалентный ему D граф и D граф в эквивалент ный магазинный автомат (языковые описания называют эквивалентными, если они задают один и тот же язык). Термины теории графов и некоторые дополни тельные термины, связанные со специфическими весами дуг, позволяют полно и точно отразить подробности работы магазинного автомата. Следует заметить, что отдельные элементы предложенной в разделе 1.2 системы понятий можно найти и в работах других авторов. Нередки также приблизительные аналоги наших поня тий и частные их случаи. Вообще, графическое представление машин Тьюринга

и их частных случаев (к которым можно отнести магазинные автоматы) имеет давнюю историю. В настоящее время графические представления магазинных автоматов обсуждаются даже в учебниках; см., например, главу 8 в [Sudkamp 97].

В разделе 1.3 определяются два существенно новых понятия: ядро Dграфа и развитие - специфическое бинарное отношение на множестве маршрутов, т.е. путей, несущих цепочки заданного Dграфом языка.

Определение развития апеллирует к понятию цикла. В нем не только охватывается, но и обобщается способ разрастания цепочек бесконтекстного языка, охарактеризованный леммой Огдена.

Ядро - это, по сути, конечное подмножество множества всех маршрутов, рассмотрение которого необходимо и достаточно для решения некоторого вопроса о Dграфе или соответствующем языке. Точнее, вводится понятие (w, б()ядра, где параметры w и d обеспечивают определенные ограничения на вхождение циклов в рассматриваемые маршруты. Величина параметров может сильно варьировать ся от задачи к задаче. Так, в том же разделе доказывается (см. теорему 4), что каждый маршрут "получается развитием"некоторого элемента (2,1)ядра. А в параграфе 3 данной главы доказывается, что, вообще говоря, только (5,5)ядро позволяет ответить на вопрос о так называемой псевдосогласуемости.

Заметим, что в доказательстве леммы 5, помогающей установить справедли -вость теоремы 4, демонстрируется специфический и весьма употребительный у нас прием доказательства фактов, формулируемых по схеме:

Если некоторый маршрут Dграфа имеет свойство P, то ядро этого Dграфа содержит маршрут со свойством P".

Прием состоит в следующем: в произвольном маршруте, обладающем свойством P, фиксируются обуславливающие его участки; в остальных участках удаляют ся все циклы, при отсутствии которых имеем все еще маршрут. Последний и является элементом ядра, параметры которого определяются числом изначально фиксированных участков и, иногда, некоторой их взаимозависимостью.

1.1. Эязыки. Понятие Dязыка обобщает понятие языка Дика, которое может быть определено, например, следующим образом.

Пусть Е( и Е) - непересекающиеся алфавиты. Пусть существует биекция

ф : Е( - Е). Тогда язык, порождаемый грамматикой

S - Л aSbS, a G Е(, b = ф(а),

назовем языком Дика.

Поведение символов в цепочках языка Дика моделирует поведение скобок. В связи с этим мы будем называть цепочки языков Дика и определяемых далее D языков скобочными системами.

Пример 1. К наименьшим по числу видов скобок в скобочных системах отно -сится язык Дика, порождаемый грамматикой

S - Л (S)S.