Проблема с высотой звезды

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

регулярных языков с неограниченной

На первый вопрос был дан отрицательный ответ, когда в 1963 году Эгган привел примеры регулярных языков со звездной высотой n для каждого n . Здесь высота звезды h ( L ) регулярного языка L определяется как минимальная высота звезды среди всех регулярных выражений, представляющих L . Первые несколько языков, найденные Эгганом, описаны ниже посредством регулярного выражения для каждого языка:

${\begin{alignedat}{2}e_{1}&=a_{1}^{*}\\e_{2}&=\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\\e_{3}&=\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\\e_{4}&=\left(\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\left(\left(a_{8}^{*}a_{9}^{*}a_{10}\right)^{*}\left(a_{11}^{*}a_{12}^{*}a_{13}\right)^{*}a_{14}\right)^{*}a_{15}\right)^{*}\end{alignedat}}$

Принцип построения этих выражений заключается в том, что выражение $e_{n+1}$ получается путем объединения двух копий $e_{n}$, соответствующим образом переименовывая буквы второй копии, используя новые символы алфавита, объединяя результат с другим новым символом алфавита, а затем окружая полученное выражение звездой Клини. Оставшаяся, более сложная часть — доказать, что для $e_{n}$ не существует эквивалентного регулярного выражения для высоты звезды меньше n ; доказательство дано у Эггана (1963) .

Однако в примерах Эггана используется большой алфавит размером 2. ^н -1 для языка с высотой звезды n . Поэтому он спросил, можем ли мы также найти примеры для двоичных алфавитов. Вскоре это подтвердили Дежан и Шютценбергер в 1966 году. Их примеры можно описать индуктивно определенным семейством регулярных выражений в двоичном алфавите. $\{a,b\}$ следующим образом – см. Саломаа (1981) :

${\begin{alignedat}{2}e_{1}&=(ab)^{*}\\e_{2}&=\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\\e_{3}&=\left(aaaa\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}bbbb\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\right)^{*}\\\,&\cdots \\e_{n+1}&=(\,\underbrace {a\cdots a} _{2^{n}}\,\cdot \,e_{n}\,\cdot \,\underbrace {b\cdots b} _{2^{n}}\,\cdot \,e_{n}\,)^{*}\end{alignedat}}$

Опять же, необходимо строгое доказательство того факта, что $e_{n}$ не допускает эквивалентного регулярного выражения для меньшей высоты звезды. Доказательства даны Дежаном и Шютценбергером (1966) и Саломаа (1981) .

Вычисление высоты звезды в обычных языках

Напротив, второй вопрос оказался гораздо более сложным, и этот вопрос стал известной открытой проблемой в теории формального языка на протяжении более двух десятилетий. В течение многих лет прогресс был незначительным. Чистогрупповые языки были первым интересным семейством регулярных языков, для которого была доказана разрешимость проблемы высоты звезды . Но общая проблема оставалась открытой более 25 лет, пока ее не разрешил Хасигути , который в 1988 году опубликовал алгоритм определения высоты звезды любого регулярного языка. Алгоритм был совершенно непрактичен, поскольку имел неэлементарную сложность . Чтобы проиллюстрировать огромное потребление ресурсов этим алгоритмом, Ломбарди и Сакарович (2002) приводят некоторые реальные цифры:

[Процедура, описанная Хасигути] приводит к вычислениям, которые совершенно невозможны даже для очень маленьких примеров. Например, если L принимается автоматом с 4 состояниями сложности цикла 3 (и с небольшим моноидом перехода из 10 элементов), то очень низкая миноранта числа языков, которые будут проверены с помощью L на равенство, равна: $\left(10^{10^{10}}\right)^{\left(10^{10^{10}}\right)^{\left(10^{10^{10}}\right)}}.$

- С. Ломбарди и Дж. Сакарович, Звездная высота обратимых языков и универсальных автоматов , LATIN 2002.

Обратите внимание, что само по себе число $10^{10^{10}}$ имеет 10 миллиардов нулей, если записать их в десятичной системе счисления , и уже намного превышает число атомов в наблюдаемой Вселенной .

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

Этот алгоритм был оптимизирован и обобщен на деревья Колкомбетом и Лёдингом в 2008 году. как часть теории регулярных функций стоимости.Он был реализован в 2017 году в наборе инструментов Stamina.

См. также

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

Ссылки

• Бжозовский, Януш А. (1980). «Открытые проблемы о регулярных языках» . В книге Рональда В. (ред.). Теория формального языка – Перспективы и открытые проблемы . Нью-Йорк: Академическая пресса. стр. 23–47 . ISBN  978-0-12-115350-2 . (версия технического отчета)
• Колкомбет, Томас; Лёдинг, Кристоф (2008). «Глубина вложенности дизъюнктивного μ-исчисления для древовидных языков и проблема ограниченности». Информатика Логика . Конспекты лекций по информатике. Том. 5213. стр. 416–430. дои : 10.1007/978-3-540-87531-4_30 . ISBN  978-3-540-87530-7 . ISSN   0302-9743 .
• Дежан, Франсуаза; Шютценбергер, Марсель-Поль (1966). «К вопросу об Эггане». Информация и контроль . 9 (1): 23–25. дои : 10.1016/S0019-9958(66)90083-0 .
• Эгган, Лоуренс К. (1963). «Графы переходов и звездность регулярных событий» . Мичиганский математический журнал . 10 (4): 385–397. дои : 10.1307/mmj/1028998975 . Збл   0173.01504 .
• Макнотон, Роберт (1967). «Петлевая сложность чисто групповых событий». Информация и контроль . 11 (1–2): 167–176. дои : 10.1016/S0019-9958(67)90481-0 .
• Саломаа, Арто (1981). Жемчужины теории формального языка . Мельбурн: Издательство Pitman Publishing. ISBN  978-0-273-08522-5 . Збл   0487.68063 .

Дальнейшее чтение

• Хасигути, Косабуро (1982). «Регулярные языки звездной высоты один». Информация и контроль . 53 (2): 199–210. дои : 10.1016/S0019-9958(82)91028-2 .
• Хасигути, Косабуро (1988). «Алгоритмы определения относительной высоты звезды и высоты звезды» . Информация и вычисления . 78 (2): 124–169. дои : 10.1016/0890-5401(88)90033-8 .
• Ломбардия, Сильвен; Сакарович, Жак (2002). «Звездная высота обратимых языков и универсальных автоматов». ЛАТИНСКИЙ 2002: Теоретическая информатика (PDF) . Конспекты лекций по информатике. Том. 2286. Спрингер. стр. 76–90. дои : 10.1007/3-540-45995-2_12 . ISBN  978-3-540-43400-9 .
• Кирстен, Дэниел (2005). «Дистанционные пустынные автоматы и проблема высоты звезды» . RAIRO - Теоретическая информатика и приложения . 39 (3): 455–509. дои : 10.1051/ita:2005027 .
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-84425-3 . Збл   1188.68177 .
• Фиялков, Натанаэль; Гимберт, Хьюго; Кельменди, Эдон; Куперберг, Денис (2017). Карайоль, Арно; Нико, Сирил (ред.). Выносливость: моноиды стабилизации в теории автоматов . ЦИАА. Чам: Международное издательство Springer. стр. 101–112. дои : 10.1007/978-3-319-60134-2_9 . ISBN  978-3-319-60134-2 .