Введение
Проблема в теории формальных языков
Проблема высоты звезды в теории формальных языков заключается в вопросе о том, можно ли все регулярные языки представить с помощью регулярных выражений ограниченной высоты звезды, то есть с ограниченной глубиной вложенности операций замыкания Клине (звёздочки). В частности, всегда ли достаточно глубины вложенности, равной единице? Если нет, существует ли алгоритм для определения необходимой глубины вложенности? Эта проблема была впервые сформулирована Эгганом в 1963 году.
Семьи регулярных языков с неограниченной высотой звезды
Первый вопрос был отвечен отрицательно, когда в 1963 году Эгган привел примеры регулярных языков звездной высоты n для каждого n. Здесь звездная высота h(L) регулярного языка L определяется как минимальная звездная высота среди всех регулярных выражений, представляющих L. Первые несколько языков, найденных Эгганом, описаны ниже путем приведения регулярного выражения для каждого языка: Принцип построения этих выражений заключается в том, что выражение получается путем конкатенации двух копий , с соответствующим переименованием букв второй копии с использованием новых символов алфавита, конкатенации результата с другим новым символом алфавита и последующим обрамлением полученного выражения звездой Клини. Более сложная часть заключается в доказательстве того, что для не существует эквивалентного регулярного выражения звездной высоты меньше n; доказательство приведено в . Однако примеры Эггана используют большой алфавит размером 2n-1 для языка со звездной высотой n. В связи с этим он задался вопросом, можно ли найти примеры над бинарными алфавитами. Это было доказано вскоре после этого Дежаном и Шютценбергером в 1966 году. Их примеры можно описать индуктивно определенным семейством регулярных выражений над бинарным алфавитом следующим образом – см. : Снова требуется строгое доказательство того, что не допускает эквивалентного регулярного выражения меньшей звездной высоты. Доказательства приведены в и в .
The construction principle for these expressions is that expression is obtained by concatenating two copies of , appropriately renaming the letters of the second copy using fresh alphabet symbols, concatenating the result with another fresh alphabet symbol, and then by surrounding the resulting expression with a Kleene star. The remaining, more difficult part, is to prove that for there is no equivalent regular expression of star height less than n; a proof is given in
However, Eggan's examples use a large alphabet, of size 2n 1 for the language with star height n. He thus asked whether we can also find examples over binary alphabets. This was proved to be true shortly afterwards by Dejean and Schützenberger in 1966. Their examples can be described by an inductively defined family of regular expressions over the binary alphabet as follows–cf. :
Again, a rigorous proof is needed for the fact that does not admit an equivalent regular expression of lower star height. Proofs are given by and by .
Вычисление звездной высоты регулярных языков
Второй вопрос оказался гораздо сложнее, и стал известной нерешенной проблемой в теории формальных языков на протяжении более двух десятилетий. На протяжении многих лет прогресс был незначительным. Первым интересным семейством регулярных языков, для которых проблема высоты звезды была доказана решаемой, стали чистые групповые языки. Однако общая проблема оставалась открытой более 25 лет, пока Хасигути не решил её, опубликовав в 1988 году алгоритм для определения высоты звезды любого регулярного языка. Алгоритм оказался совершенно непрактичным из-за неэлементарной сложности. Чтобы проиллюстрировать колоссальное потребление ресурсов этим алгоритмом, приведем некоторые конкретные цифры: обратите внимание, что само число содержит 10 миллиардов нулей при записи в десятичной системе счисления и уже во много раз превышает количество атомов в наблюдаемой Вселенной. Гораздо более эффективный алгоритм, чем процедура Хасигути, был разработан Кирстеном в 2005 году. Этот алгоритм, принимая на вход недетерминированный конечный автомат, работает в двойном экспоненциальном пространстве. Тем не менее, требования к ресурсам этого алгоритма всё ещё значительно превышают пределы практически осуществимого. В 2008 году Колкомбе и Лёдинг оптимизировали и обобщили этот алгоритм для деревьев в рамках теории регулярных функций стоимости. В 2017 году он был реализован в инструментальном комплексе Stamina.
Notice that alone the number has 10 billion zeros when written down in decimal notation, and is already by far larger than the number of atoms in the observable universe. A much more efficient algorithm than Hashiguchi's procedure was devised by Kirsten in 2005. This algorithm runs, for a given nondeterministic finite automaton as input, within double exponential space. Yet the resource requirements of this algorithm still greatly exceed the margins of what is considered practically feasible. This algorithm has been optimized and generalized to trees by Colcombet and Löding in 2008, as part of the theory of regular cost functions. It has been implemented in 2017 in the tool suite Stamina.