Кіріспе
Формалды тіл теориясындағы мәселе
Формалды тіл теориясындағы жұлдыз биіктігі мәселесі – барлық тұрақты тілдерді шектеулі жұлдыз биіктігімен, яғни Клейне жұлдыздарының шектеулі ұялау тереңдігі бар тұрақты өрнектерді қолдану арқылы өрнектеуге бола ма деген сұрақ. Атап айтқанда, ұялау тереңдігінің біреуі әрқашан жеткілікті ме? Егер жеткіліксіз болса, қажетті ұялау тереңдігін анықтайтын алгоритм бар ма? Бұл мәселені алғаш рет 1963 жылы Эгган ұсынды.
Жұлдыз биіктігі шектелмеген тұрақты тілдер отбасылары
Бірінші сұраққа 1963 жылы Эгган әр n үшін n жұлдыз биіктігі бар тұрақты тілдердің мысалдарын келтіргенде теріс жауап берілді. Мұнда L тұрақты тілінің жұлдыз биіктігі h(L) – L-ді білдіретін барлық тұрақты өрнектер арасындағы ең төменгі жұлдыз биіктігі ретінде анықталады. Эгган тапқан алғашқы бірнеше тілдер төменде әр тіл үшін тұрақты өрнек берілу арқылы сипатталған: Бұл өрнектерді құру принципі – өрнектің екі көшірмесін біріктіру, екінші көшірменің әріптерін жаңа әліпби символдарын пайдаланып өзгерту, нәтижені тағы бір жаңа әліпби символымен біріктіру, содан кейін алынған өрнекті Клейне жұлдызымен қоршау. Қалған, қиын бөлігі – n-ден төмен жұлдыз биіктігі бар эквивалентті тұрақты өрнек жоқ екенін дәлелдеу; дәлелдемесі берілген. Дегенмен, Эгганның мысалдары жұлдыз биіктігі n болатын тіл үшін 2n-1 өлшеміндегі үлкен әліпбиді қолданады. Ол, демек, екілік әліпбилер бойынша да мысалдар табу мүмкін бе деп сұрады. Бұл 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 құралдар жиынтығында іске асырылды.