Высота звезды

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

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

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

$\textstyle h\left(\emptyset \right)\,=\,0$ , $\textstyle h\left(\varepsilon \right)\,=\,0$ , и $\textstyle h\left(a\right)\,=\,0$ для всех символов алфавита a в A .
$\textstyle h\left(EF\right)\,=\,h\left(E\,\mid \,F\right)\,=\,\max \left(\,h(E),h(F)\,\right)$
$\textstyle h\left(E^{*}\right)\,=\,h(E)+1.$

Здесь, $\scriptstyle \emptyset$ – специальное регулярное выражение, обозначающее пустое множество, а ε – специальное, обозначающее пустое слово ; E и F — произвольные регулярные выражения.

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

Примеры

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

\textstyle \left(b\,\mid \,aa^{*}b\right)^{*}aa^{*}

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

\textstyle (a\,\mid \,b)^{*}a

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

Звездная высота группового языка вычислима: например, звездная высота языка над { a , b }, в которой количество вхождений a и b конгруэнтно по модулю 2. ^н это н . ^[1]

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

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

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

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

Если G ациклична , то $r (G) = 0$ . Это применимо, в частности, если G пуст.
Если G и сильно связна E непусто , то

r(G)=1+\min _{v\in V}r(G-v),\,

где ⁠

G-v

⁠ — это орграф, полученный в результате удаления вершины

v

и всех ребер, начинающихся или заканчивающихся в

v

.

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

В теории автоматов недетерминированный конечный автомат с ε-переходами (ε-NFA) определяется как из 5 элементов ( Q , Σ, δ , q0 _, набор F ), состоящий из

конечное множество состояний Q
конечное множество входных символов Σ
набор помеченных ребер δ , называемый отношением перехода : Q × (Σ ∪{ε}) Q. × Здесь ε обозначает пустое слово .
начальное состояние q ₀ ∈ Q
набор состояний F, отличающихся как принимающие состояния F ⊆ Q .

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

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

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

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

Обобщенная высота звезды

Приведенное выше определение предполагает, что регулярные выражения строятся из элементов алфавита A. используя только стандартные операторы set Union , Concatenation и Star Клини . Обобщенные регулярные выражения определяются так же, как и регулярные выражения, но здесь также установки дополнения. разрешен оператор (дополнение всегда берется по множеству всех слов над A). Если мы изменим определение так, чтобы принятие дополнений не увеличивало высоту звезды, то есть

\textstyle h\left(E^{c}\right)\,=\,h(E)

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

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

\textstyle (a\,\mid \,b)^{*}a,

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

\textstyle \emptyset ^{c}a

,

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

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

См. также

Ссылки

^ Сакарович (2009) стр.342

Берстель, Жан; Ройтенауэр, Кристоф (2011), Некоммутативные рациональные ряды с приложениями , Энциклопедия математики и ее приложений, том. 137, Кембридж: Издательство Кембриджского университета , ISBN 978-0-521-19022-0 , Збл 1250.68007
Коэн, Рина С. (1971), «Методы определения высоты звезд регулярных множеств», Теория вычислительных систем , 5 (2): 97–114, doi : 10.1007/BF01702866 , ISSN 1432-4350 , S2CID 1970902 , Zbl 0218.94028
Коэн, Рина С.; Бжозовский, Дж. А. (1970), «Общие свойства высоты звезды регулярных событий», Журнал компьютерных и системных наук , 4 (3): 260–280, doi : 10.1016/S0022-0000(70)80024-1 , ISSN 0022 -0000 , Збл 0245.94038
Эгган, Лоуренс К. (1963), «Графы переходов и высота звезды регулярных событий», Michigan Mathematical Journal , 10 (4): 385–397, doi : 10.1307/mmj/1028998975 , Zbl 0173.01504
Сакарович, Жак (2009), Элементы теории автоматов , Перевод с французского Рубена Томаса, Кембридж: Cambridge University Press , ISBN 978-0-521-84425-3 , Збл 1188,68177
Саломаа, Арто (1981), Драгоценности теории формального языка , Роквилл, Мэриленд: Computer Science Press, ISBN 978-0-914894-69-8 , Збл 0487.68064
Шютценбергер, член парламента (1965), «О конечных моноидах, имеющих только тривиальные подгруппы», Information and Control , 8 (2): 190–194, doi : 10.1016/S0019-9958(65)90108-7 , ISSN 0019-9958 , Zbl 0131.02001

[Sak342-1] Сакарович (2009) стр.342

[1]