Высота итерации языка

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

Формальное определение

Формально, высота итерации регулярного выражения E над конечным алфавитом A определяется индуктивно следующим образом:

• [math]\displaystyle{ \scriptstyle h\left(\emptyset\right)\,=\,0 }[/math], [math]\displaystyle{ \scriptstyle h\left(\varepsilon\right)\,=\,0 }[/math] и [math]\displaystyle{ \scriptstyle h\left(a\right)\,=\,0 }[/math] для любого символа a из алфавита A.
• [math]\displaystyle{ \scriptstyle h\left(E F\right)\,=\, h\left(E\, \mid\, F\right)\,=\,\max \left(\, h(E), h(F)\,\right) }[/math]
• [math]\displaystyle{ \scriptstyle h\left(E^*\right)\,=\,h(E)+1. }[/math]

Здесь [math]\displaystyle{ \scriptstyle \emptyset }[/math] обозначает пустое множество, ε означает пустую строку, а E и F — произвольные регулярные выражения.

Высота итерации h(L) регулярного языка L определяется как минимальная высота итерации всех регулярных выражений, представляющих L. Интуитивно понятно, что если язык L имеет высокую высоту итерации, он сам по себе сложен, поскольку не может быть описан в терминах «простых» регулярных выражений с низкой высотой итерации.

Примеры

Хотя вычисление высоты итерации регулярного выражения просто, определения высоты итерации языка может иногда оказаться запутанным. В качестве примера регулярное выражение

[math]\displaystyle{ \scriptstyle \left(b\, \mid\, a a^*b\right)^*a a^* }[/math]

над алфавитом A = {a, b} имеет высоту итерации 2. Однако описываемый язык представляет собой множество всех слов, оканчивающихся на a. Тот же язык можно описать с помощью выражения

[math]\displaystyle{ \scriptstyle (a\, \mid\, b)^*a }[/math],

высота итерации которого лишь 1. Чтобы доказать, что высота итерации языка равна 1, нужно исключить возможность описания языка регулярным выражением с меньшей высотой итерации. Например, это может быть сделано косвенно путём доказательства, что язык с высотой итерации 0 содержит лишь конечное число слов. Поскольку наш язык бесконечен, он не может иметь высоту итерации 0.

Высота итерации группового языка вычислима. Например, высота итерации языка над {a,b}, в котором число вхождений a и b сравнимы по модулю 2ⁿ, равна n.

Теорема Эггана

Пример автомата с циклическим рангом 1. Алгоритм Клини преобразует его в регулярное выражение a^*b^*ba ((a|b)b^*a|ε)^* (a|b)b^* | a^*b^*b, которое имеет высоту итерации 2. По теореме Эггана должно существовать эквивалентное регулярное выражение с высотой итерации ≤1 must exist. Фактически a^*b(b|a(a|b))^* описывает тот же язык.

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

В теории графов циклический ранг r(G) ориентированного графа (орграфа) G = (V, E) определяется индуктивно следующим образом:

• Если G является ацикличным, r(G) = 0. Циклический ранг равен нулю также в случае пустого графа G.
• Если G строго связен и E не пусто, то

[math]\displaystyle{ r(G) = 1 + \min_{v\in V} r(G-v),\, }[/math] где G — v — орграф, полученный удалением вершины v и всех дуг, имеющих v в качестве начала или конца.

• Если G не строго связен, то r(G) равен максимальному циклическому рангу среди всех строго связных компонент графа G.

В теории автоматов недетерминированный конечный автомат с ε-переходами (ε-НКА) определяется как кортеж (Q, Σ, δ, q₀, F), состоящий из

• конечного множества состояний Q
• конечного множества входных символов Σ
• множества помеченных дуг δ, называемых переходами: [math]\displaystyle{ Q \times (\Sigma \cup \{\varepsilon\}) \times Q }[/math]. Здесь ε обозначает пустую строку.
• начальное состояние q₀ ∈ Q
• множество состояний F, называемых поглощающими, F ⊆ Q.

Слово w ∈ Σ^* принимается ε-НКА, если существует ориентированная цепь из начального стостояния q₀ до некоторого конечного состояния F, использующая диги из δ, так что конкатенация всех меток вдоль пути образует слово w. Множество всех слов над Σ^*, принимаемых автоматом, является языком, принимаемым автоматом A.

Если говорить о недетерминированном конечном автомате A со множеством состояний Q как об ориентированном графе, мы естественным образом имеем в виду граф с множеством вершин Q, порождённым переходами. Теперь можно сформулировать теорему.

Теорема Эггана: Высота итерации регулярного языка L равна наименьшему циклическому рангу среди всех недетерминированных конечных автоматов с ε-переходами, принимающих язык L.

Доказательство этой теоремы дал Эгган, и, позднее, Сакарович.

Обобщённая проблема высоты итерации

Вышеприведённое определение предполагает, что регулярное выражение строится на элементах алфавита A, используя только стандартные операции объединения множеств, конкатенации и замыкания Клини. Обобщённое регулярное выражение определяется как регулярное выражение, но включает также операцию дополнение множества (дополнение всегда берётся относительно всех слов над A). Если мы будем считать, что взятие дополнения не увеличивает высоту итерации, то есть

[math]\displaystyle{ \scriptstyle h\left(E^c\right)\,=\,h(E) }[/math],

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

Заметим, что в то время как языки с нулевой (обычной) высотой итерации содержат конечное число слов, существуют бесконечные языки с нулевой обобщённой высотой итерации.

Пример. Регулярное выражение

[math]\displaystyle{ \scriptstyle (a\, \mid\, b)^*a, }[/math]

которое мы видели в примере выше, можно эквивалентно переписать как обобщённое регулярное выражение

[math]\displaystyle{ \scriptstyle \emptyset^c a }[/math],

поскольку дополнение пустого множества — это в точности все слова над алфавитом A. Таким образом, множество всех слов над алфавитом A, кончающихся буквой a, имеют высоту итерации один, в то время как обобщённая высота итерации равна нулю.

Языки с нулевой высотой итерации называются языками без звёздочек. Можно показать, что язык L является языком без звёздочек тогда и только тогда, когда его cинтаксический моноид является апериодичным.

См. также

• Проблема высоты итерации языка
• Обобщённая проблема высоты итерации языка

Литература

• Jean Berstel, Christophe Reutenauer. Noncommutative rational series with applications. — Cambridge: Cambridge University Press, 2011. — Т. 137. — (Encyclopedia of Mathematics and Its Applications). — ISBN 978-0-521-19022-0.
• Rina S. Cohen. Techniques for establishing star height of regular sets // Theory of Computing Systems. — 1971. — Т. 5, вып. 2. — С. 97—114. — ISSN 1432-4350. — doi:10.1007/BF01702866.
• Rina S. Cohen, J.A. Brzozowski. General properties of star height of regular events // Journal of Computer and System Sciences. — 1970. — Т. 4, вып. 3. — С. 260—280. — ISSN 0022-0000. — doi:10.1016/S0022-0000(70)80024-1.
• Lawrence C. Eggan. Transition graphs and the star-height of regular events // Michigan Mathematical Journal. — 1963. — Т. 10, вып. 4. — С. 385—397. — doi:10.1307/mmj/1028998975.
• Jacques Sakarovitch. Elements of automata theory. — Cambridge: Cambridge University Press, 2009. — ISBN 978-0-521-84425-3.
• Arto Salomaa. Jewels of formal language theory. — Rockville, Maryland: Computer Science Press, 1981. — ISBN 0-914894-69-2.
• M.P. Schützenberger. On finite monoids having only trivial subgroups // Information and Control. — 1965. — Т. 8, вып. 2. — С. 190—194. — ISSN 0019-9958. — doi:10.1016/S0019-9958(65)90108-7.