Высота звезды - Star height

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

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

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

• ${ Displaystyle textstyle ч влево ( emptyset вправо) , = , 0}$, ${ Displaystyle textstyle ч влево ( varepsilon right) , = , 0}$, и ${ Displaystyle textstyle ч влево (а вправо) , = , 0}$ для всех символов алфавита а в А.
• ${ Displaystyle textstyle ч влево (EF вправо) , = , ч влево (E , середина , F вправо) , = , макс влево (, ч (E), h (F) , right)}$
• ${ displaystyle textstyle h left (E ^ {*} right) , = , h (E) +1.}$

Вот, ${ Displaystyle scriptstyle emptyset}$ - специальное регулярное выражение, обозначающее пустое множество, а ε - специальное выражение, обозначающее пустое слово; E и F - произвольные регулярные выражения.

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

Примеры

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

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

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

${ Displaystyle textstyle (а , середина , Ь) ^ {*} а}$

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

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

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

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

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

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

• Если г является ациклический, тогда р(г) = 0. Это особенно важно, если г пусто.
• Если г является сильно связанный и E непусто, то

${ Displaystyle г (G) = 1 + мин _ {v in V} г (G-v), ,}$ где ${ displaystyle G-v}$ орграф, полученный в результате удаления вершины v и все ребра, начинающиеся или заканчивающиеся на v.

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

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

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

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

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

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

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

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

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

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

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

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

${ Displaystyle textstyle (а , середина , Ь) ^ {*} а,}$

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

${ displaystyle textstyle emptyset ^ {c} a}$,

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

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

Смотрите также

• Проблема высоты звезды
• Обобщенная проблема высоты звезды.

использованная литература

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