регулярные выражения
Можно построить один конечный автомат, который будет проверять удовлетворяет ли строка одновременно обоим регэкспам. Потом проверить является ли конечное состояние достижимым.
Средний человек в теме разрюхает за пару дней, при условии простых регэксп выражений. Если ж нужны всякие lookahead'ы, и прочие навороты, это займет больше.
Средний человек в теме разрюхает за пару дней, при условии простых регэксп выражений. Если ж нужны всякие lookahead'ы, и прочие навороты, это займет больше.
регулярные выражения перл
Я бы предложил проверить сначала один регэксп, потом другой, и применить к результатам логический оператор И, если бы это не было настолько очевидно.
Мой вариант просто предполагает написание своего парсера регэкспов. Не думаю, что задача решается без этого.
Поэтому если нужны все фичи перловского регэкспа, то это будет затык. А любое ограничение на поддерживаемые конструкции будет неплохим облегчением.
Хотя, если к перлу есть сурсы, и программист будет рюхающим... То все возможно =)
Поэтому если нужны все фичи перловского регэкспа, то это будет затык. А любое ограничение на поддерживаемые конструкции будет неплохим облегчением.
Хотя, если к перлу есть сурсы, и программист будет рюхающим... То все возможно =)
Так то это так, конечно, но задача формулировалась несколько иначе, чем ты, очевидно, подумал
"Требуется определить существует ли строка которая подходит к обоим выражениям."
"Требуется определить существует ли строка которая подходит к обоим выражениям."
а есть способ узнать, есть ли строка, которая подходит данному регулярному выражению?
Вообще, в общем случае эта задача не разрешима, из матлогических соображений. Ни определить, одинаковые ли регулярные выражения, ни о существовании общей строки. Причём вторая задача (которая и требуется) сложнее, и скорее возникнет ситуация, когда задачу решить будет невозможно.
Однако в простых и ограниченных частных случаях решение придумать можно.
Однако в простых и ограниченных частных случаях решение придумать можно.
Способ есть, и он написан в первом моем посте здесь.
Каждое регулярное выражение парсится, и ему в соответсвие ставится простейший конечный автомат, который и проверяет принадлежность строки регэкспу.
Если непонятно, что такое конечный автомат - в гугл.
Если нужна дока, как регэкспу поставить в соответсвие конечный автомат - можно написать мне в приват, у меня где то пдфка валялась на эту тему...
Теперь, когда есть конечный автомат, все просто. Это фактически граф, в котором надо проверить достижимость определенной вершины, называемой конечной. Тот же поиск в ширину сойдет, по пути и сама строка построится. Причем минимальная =)
Каждое регулярное выражение парсится, и ему в соответсвие ставится простейший конечный автомат, который и проверяет принадлежность строки регэкспу.
Если непонятно, что такое конечный автомат - в гугл.
Если нужна дока, как регэкспу поставить в соответсвие конечный автомат - можно написать мне в приват, у меня где то пдфка валялась на эту тему...
Теперь, когда есть конечный автомат, все просто. Это фактически граф, в котором надо проверить достижимость определенной вершины, называемой конечной. Тот же поиск в ширину сойдет, по пути и сама строка построится. Причем минимальная =)
Ммм. В свете поста выше, ты утверждаешь, что нельзя определить достижимость конечного состояния автомата?
Вот с эквивалентностью конечных автоматов дело сложнее. Но и тут решение скорее есть, чем его нет.
А ты, наверное, путаешь это с чем-нибудь, вроде построения такого алгоритма, который за конечное время определит зациклится ли другой поданный на вход алгоритм при заданном input'е.
Это совершенно разные постановки задач.
Вот с эквивалентностью конечных автоматов дело сложнее. Но и тут решение скорее есть, чем его нет.
А ты, наверное, путаешь это с чем-нибудь, вроде построения такого алгоритма, который за конечное время определит зациклится ли другой поданный на вход алгоритм при заданном input'е.
Это совершенно разные постановки задач.
да, недоглядел
Регексы с "лукахедами и прочими наворотами" не являются регулярными выражениями, а конкретно тот набор наворотов, который встроен в .НЕТ регекс енджин, делает их равными по мощности машинам тьюринга. А перловый набор вроде почти такой же.
Да, с этим я поторопился.
Всем участникам - извинения =)
Всем участникам - извинения =)
был уже сходный тред, поднимите поиск
Щас вот тут подумал еще.
Лукахед/лукбехайнд точно не нарушает регулярности множества. Это очевидно, так как эти лукахеды имеют смысл только в реплейсах.
Бэкреференс - для задачи существования строки это дело обходится. Например, если надо получить на выходе просто true/false, этот бэкреференс можно просто выкинуть из регэкспа.
Ну а больше нарушающих регулярность фич в перле я не нашел. Хотя мог что то и пропустить. Если пропустил - просвятите.
Так что проверить существование строки удовлетворяющей одному регэкспу пожалуй можно. А вот одновременно двум - это вопрос. Потому что склеивать конечные автоматы с учетом бэкреференсов - тут надо думать =)
Лукахед/лукбехайнд точно не нарушает регулярности множества. Это очевидно, так как эти лукахеды имеют смысл только в реплейсах.
Бэкреференс - для задачи существования строки это дело обходится. Например, если надо получить на выходе просто true/false, этот бэкреференс можно просто выкинуть из регэкспа.
Ну а больше нарушающих регулярность фич в перле я не нашел. Хотя мог что то и пропустить. Если пропустил - просвятите.
Так что проверить существование строки удовлетворяющей одному регэкспу пожалуй можно. А вот одновременно двум - это вопрос. Потому что склеивать конечные автоматы с учетом бэкреференсов - тут надо думать =)
Вообще, в общем случае эта задача не разрешима, из матлогических соображений.Уже пора написать в ФАК ссылки какие-нибудь на "теоретические основания" так сказать регулярных выражений, чтобы можно было сразу отправлять вот таких вот
делает их равными по мощности машинам тьюрингаА сцылочку можно?
вообще видимо проблема распознования принадлежности слова языку, порожденному рег-м выр. перла не является сложной - ведь с ними работает перл и тотже jakarta oro
Может ли мне это как то помочь(в том числе наличие библиотек для распознавания принадлежности слова регулярному выражению)
Может ли мне это как то помочь(в том числе наличие библиотек для распознавания принадлежности слова регулярному выражению)
> а конкретно тот набор наворотов, который встроен в .НЕТ регекс енджин, делает их равными по мощности машинам тьюринга
Поскольку задача определения завершится ли некоторая программа на машине Тьюринга или нет алгоритмически неразрешима, то получается, что задача определения подходит ли строка под .NET regex engine тоже алгоритмически неразрешима? lol
Поскольку задача определения завершится ли некоторая программа на машине Тьюринга или нет алгоритмически неразрешима, то получается, что задача определения подходит ли строка под .NET regex engine тоже алгоритмически неразрешима? lol
может это просто значит, что с помощью выражения её можно повесить? равно как и с помощью while(1)?
какая-то по-моему уже еруда пошла.
Если язык не регулярный то он не распознается автоматами, но может хорошо распозноваться машинами Тьюринга.
Если язык не регулярный то он не распознается автоматами, но может хорошо распозноваться машинами Тьюринга.
> может это просто значит, что с помощью выражения её можно повесить? равно как и с помощью while(1)? Круто! Интересно посмотреть на такое живьем. У кого есть доступ к .NET regex engine --- проверьте, плз.
если упоминание про машину Тьюринга так сразу зацикливание - это не так.
Ни определить, одинаковые ли регулярные выраженияне правда - эта задача разрешима, также разрешима задача элементарности регулярного выражения... так что ждем ссылок
Ну типа это.
The following expression matches all balanced opening and closing angle brackets(<>). Angle brackets were used because they do no require escaping like parenthesis and make the expression a little easier to read:
То есть это уже где-то в КС грамматиках.
Насчёт эквивалентности машине Тьюринга я скорее всего нагнал. Хотя наверняка не скажу - наличие (?< в которую тоже можно вставлять добавление/удаление групп делает всё жутко интересным.
The following expression matches all balanced opening and closing angle brackets(<>). Angle brackets were used because they do no require escaping like parenthesis and make the expression a little easier to read:
<
[^<>]*
(
(
(?<Open><)
[^<>]*
)+
(
(?<Close-Open>>)
[^<>]*
)+
)*
(?(Open?!
>
То есть это уже где-то в КС грамматиках.
Насчёт эквивалентности машине Тьюринга я скорее всего нагнал. Хотя наверняка не скажу - наличие (?< в которую тоже можно вставлять добавление/удаление групп делает всё жутко интересным.
Это, вообще говоря, уже не регулярное выражение. Т.е. класс языков, порождаемых подобными выражениями шире регулярного.
Ну да. А я о чём? =)
То, что я писал про невозможность определения, существуют ли последовательность, удовлетворяющая регулярному выражению - это я протормозил, это возможно. Насчёт того, можно ли найти общую последовательность для двух регулярных выражений - здесь я совсем не уверен. Это если рассматривать классические регулярные выражения, сводимые к конечным автоматам. Проблема же определения общей последовательности кроется в том, что одному состоянию, вообще говоря, может соответствовать очень много достаточно хитрых последовательностей, причём бесконечное число... Пример - если мы рассматриваем последовательности вида baaaaa(много a)aab.
Общее регулярное выражение для неё - "ba+b". Теперь можно взять частные случаи - последовательности, вида "b(a{71})+b" и "b(a{73})+b", то есть последовательности, в которых число вхождений a кратно 71 и 73 соответственно. Тогда общая последовательность для них будет содержать число a кратное 71*73=5183. Можно понять, куда я клоню - можно придумать куда более извращённые примеры.
О нестандартных регулярных выражениях - я про них ничего просто не знаю. Здесь сказали, что в C# подобное, поэтому я и высказал гипотезу о теоретической возможности подвесить машину. Вопрос - можно ли составить регулярное выражение, которое:
1) отлавливает последовательности вида ca{n}b{n}c - то есть последовательности, где число a и b равно, но заранее неизвестно
2) отлавливает последовательности вида ba{n*n}b - то есть последовательности, где число вхождений a - это квадрат целого числа.
Конечный автомат для отлова таких последовательностей построить невозможно. Есть подозрение, что если разборщик позволяет обрабатывать подобные выражения (конечно, в другой записи то можно доказать, что существуют 2 выражения, доказать существование или невозможность существования общих последовательностей для которых невозможно. Пусть кто-нибудь пример выражений для нахождения 1) и 2) приведёт - можно будет подумать над конкретным примером.
Общее регулярное выражение для неё - "ba+b". Теперь можно взять частные случаи - последовательности, вида "b(a{71})+b" и "b(a{73})+b", то есть последовательности, в которых число вхождений a кратно 71 и 73 соответственно. Тогда общая последовательность для них будет содержать число a кратное 71*73=5183. Можно понять, куда я клоню - можно придумать куда более извращённые примеры.
О нестандартных регулярных выражениях - я про них ничего просто не знаю. Здесь сказали, что в C# подобное, поэтому я и высказал гипотезу о теоретической возможности подвесить машину. Вопрос - можно ли составить регулярное выражение, которое:
1) отлавливает последовательности вида ca{n}b{n}c - то есть последовательности, где число a и b равно, но заранее неизвестно
2) отлавливает последовательности вида ba{n*n}b - то есть последовательности, где число вхождений a - это квадрат целого числа.
Конечный автомат для отлова таких последовательностей построить невозможно. Есть подозрение, что если разборщик позволяет обрабатывать подобные выражения (конечно, в другой записи то можно доказать, что существуют 2 выражения, доказать существование или невозможность существования общих последовательностей для которых невозможно. Пусть кто-нибудь пример выражений для нахождения 1) и 2) приведёт - можно будет подумать над конкретным примером.
как ни странно, задача решается путем построения автомата, являющегося прямым произведением двух исходных.
Если конечное состояние такого автомата достижимо из начального, то такое слово существует и его можно построить выписав метки на ребрах соотв. пути.
понятно как такой автомат строить?
Если конечное состояние такого автомата достижимо из начального, то такое слово существует и его можно построить выписав метки на ребрах соотв. пути.
понятно как такой автомат строить?
Пример для нахождения первого ты без труда можешь получить из моего скобочкосчитателя, убрав внешнюю *
да, плюс ко всему: если кол-ва переходов в исходных автоматах N и M, сто сложность такой проверки есть O(N*M а минимальная длина слова, соотв и первому и второму не более N*M.
Есть подозрение, что если разборщик позволяет обрабатывать подобные выражения (конечно, в другой записи то можно доказать, что существуют 2 выражения, доказать существование или невозможность существования общих последовательностей для которых невозможно. Пусть кто-нибудь пример выражений для нахождения 1) и 2) приведёт - можно будет подумать над конкретным примером.Надо определиться с возможными выражениями.
Просто если рассматривать счетные языки (пусть не регулярные то пересечение двух языков мы построить все-таки сможем. То есть, если общее слово будет, то за конечное время (но не факт, что за заранее ограниченое) мы сможем найти его
Пока я его не очень понимаю, видимо почитать про это нужно чего-нибудь... Кроме того, у меня нет C#, поэтому хорошо бы пример для perl, если такое возможно (здесь упоминалось, что для perl такое тоже возможно).
Насчёт нахождения последовательностей для обычных автоматов - убедил.
Что касается построения примеров - вот, например, берём Б. теорему Ферма (очень хорошая вещь для построения подобных примеров). Записываем две последовательности выражениями вида
"ba{n*n*n}b" и "ba{m*m*m}a{n*n*n}b".
Найдя общее решение - найдём частное решение (которого не существует не найдя - построим доказательство несуществования решения для конкретной степени (в данном случае - 3). Можно решать и другие задачи, менее именитые, но решать которые на компьютере алгоритмически тяжело - то есть расширив запись регулярный выражений, мы явно уходив в другой класс задач, значительно более сложный.
Что такое "произведение конечных автоматов"? Проблема в том, что конечный автомат не может хранить ни последовательностей, ни чисел, а состояние автомата может задавать бесконечное число последовательностей. И пока я не представляю, как сделать хотя бы 2 автомата, чтобы при заранее неизвестном n при последовательности вида ca{n}b{n}c они оба попадали в одно (своё для каждого состояния а иначе хотя бы один из них - в другое.
Просто если рассматривать счетные языки (пусть не регулярные то пересечение двух языков мы построить все-таки сможем. То есть, если общее слово будет, то за конечное время (но не факт, что за заранее ограниченое) мы сможем найти егоНу в том момент, когда слово будет найдено, время по определению станет конечным, а пока оно не найдено, можно прождать счётное время, и при этот будет непонятно, что происходит
Что касается построения примеров - вот, например, берём Б. теорему Ферма (очень хорошая вещь для построения подобных примеров). Записываем две последовательности выражениями вида
"ba{n*n*n}b" и "ba{m*m*m}a{n*n*n}b".
Найдя общее решение - найдём частное решение (которого не существует не найдя - построим доказательство несуществования решения для конкретной степени (в данном случае - 3). Можно решать и другие задачи, менее именитые, но решать которые на компьютере алгоритмически тяжело - то есть расширив запись регулярный выражений, мы явно уходив в другой класс задач, значительно более сложный.
Что такое "произведение конечных автоматов"? Проблема в том, что конечный автомат не может хранить ни последовательностей, ни чисел, а состояние автомата может задавать бесконечное число последовательностей. И пока я не представляю, как сделать хотя бы 2 автомата, чтобы при заранее неизвестном n при последовательности вида ca{n}b{n}c они оба попадали в одно (своё для каждого состояния а иначе хотя бы один из них - в другое.
да, время конечное.
но в такой постановке время не обязательно заранее ограничено каким-либо числом.
но в такой постановке время не обязательно заранее ограничено каким-либо числом.
Просто если рассматривать счетные языки (пусть не регулярные то пересечение двух языков мы построить все-таки сможем.Это верно только для рекурсивных языков. В общем случае алгоритмически может быть невозможно определить принадлежит ли слово языку.
ЗЫ. хз что там в C#, а вот язык перловых регэкспов точно полон по Тьюрингу
ЗЗЫ. там довольно легко можно сделать виснущий регэксп - qr{ (?{ while (1) {} }) }x
> Что такое "произведение конечных автоматов"?
У произведения конечных автоматов множество вершин это все упорядоченные попарные сочетания вершин автомата А и автомата Б (произведение множеств как оно есть). Дальше логичным образом расставляешь переходы - из AiBj по символу х в состояние AkBl если есть переход из Ai-x->Ak и Bj-x->Bl. Дальше волной ищешь путь из начального в конечное.
Так что если мы в классе регулярных выражений, то всё заебись.
У произведения конечных автоматов множество вершин это все упорядоченные попарные сочетания вершин автомата А и автомата Б (произведение множеств как оно есть). Дальше логичным образом расставляешь переходы - из AiBj по символу х в состояние AkBl если есть переход из Ai-x->Ak и Bj-x->Bl. Дальше волной ищешь путь из начального в конечное.
Так что если мы в классе регулярных выражений, то всё заебись.
О! только вот прочитал этот кусок твоего поста:
А вот на счет остального я в этой цитате, я вообще не могу понять что именно ты хотел сказать
На чсет произведения автоматов Fj все правильно написал вроде.
Что такое "произведение конечных автоматов"? Проблема в том, что конечный автомат не может хранить ни последовательностей, ни чисел, а состояние автомата может задавать бесконечное число последовательностей. И пока я не представляю, как сделать хотя бы 2 автомата, чтобы при заранее неизвестном n при последовательности вида ca{n}b{n}c они оба попадали в одно (своё для каждого состояния а иначе хотя бы один из них - в другое.
А вот на счет остального я в этой цитате, я вообще не могу понять что именно ты хотел сказать
Это верно только для рекурсивных языков. В общем случае алгоритмически может быть невозможно определить принадлежит ли слово языку.Да. вроде так. просто не знал об рекурсивных язаках, поэтому сказал как смог. Посмотрел кое-что по рекурсивным языкам.
Только вот кажется, что мое утверждение также будет верным для рекурсивно перечислимых, но не рекурсивных.
Нам не надо распознавать язык. Надо лишь генерировать слова из него.
Я имел в виду, что если взять два конечных автомата X,Y, в оба автомата подавать последовательности c_i, и смотреть на состояние (x_i,y_i то и в такой постановке я не понимаю, как создать автомат, отлавливающий последовательности вида "ca{n}b{n}c" - собственно, из такого двойного автомата можно составить одинарный. Если же мы можем подавать в автомат одновременно два элемента, из разных участков последовательности - то в принципе, при некоторой логике автомата (которая не предусмотрена в конечном автомате) подобное отловить уже возможно. А насчёт того, что классическим конечным автоматом такие последовательности отловить невозможно - в этом я уверен абсолютно.
Только вот кажется, что мое утверждение также будет верным для рекурсивно перечислимых, но не рекурсивных.врятли
если можно сгенерить (программой) пересечение рекурсивно перечеслимого языка с конечным (что не сложнее чем со счетным рек. перечислимым то получится что мы пересекая с языками из одного слова сможем распозновать слова первого языка => он рекурсивный
Понял.
Видимо нужно прояснить ситуацию:
1. Когда я говорил про произведение автоматов это касалось первоначальной постановки задачи.
То есть рассматривал ситуацию, когда даны два регулярных выражения в классическом смысле. Тогда проверить имеют ли соответствующие регулярные языки непустое пересечение можно посредством построения прямого произведения исходных автоматов.
Замечу, что "ca{n}b{n}c" к такому случаю никакого отношения не имеет.
2. По поводу совсем произвольного случая --- рекурсивно представимых языков (таких, слова которых можно вычислить при помощи программы) я также высказывался, что самым тупым перебором мы когда-нибудь да найдем пересечение, если оно есть.
3. А на счет "расширенных регулярных" языков, про которые ты говоришь сейчас, я ничего не могу сказать конкретного, пока задача полностью не формализована.
А по поводу того, что ты написал, конечно прямое произведение в таком случае нифига не поможет, т.к. язык, порождаемый "ca{n}b{n}c" не является регулярным (а прямое произведение регулярных есть регулярный). Почему это так? --- не помню. Вроде когда-то что-то читал про это. Есть какие-то теоремы на этот счет. В любом случае не стоит изобретать вилосипед и лучше ознакомиться с существующей теорией. Ты наверняка сможешь найти что-нибудь полезное и интересное, если попробуешь вылезть в инет.
Видимо нужно прояснить ситуацию:
1. Когда я говорил про произведение автоматов это касалось первоначальной постановки задачи.
То есть рассматривал ситуацию, когда даны два регулярных выражения в классическом смысле. Тогда проверить имеют ли соответствующие регулярные языки непустое пересечение можно посредством построения прямого произведения исходных автоматов.
Замечу, что "ca{n}b{n}c" к такому случаю никакого отношения не имеет.
2. По поводу совсем произвольного случая --- рекурсивно представимых языков (таких, слова которых можно вычислить при помощи программы) я также высказывался, что самым тупым перебором мы когда-нибудь да найдем пересечение, если оно есть.
3. А на счет "расширенных регулярных" языков, про которые ты говоришь сейчас, я ничего не могу сказать конкретного, пока задача полностью не формализована.
А по поводу того, что ты написал, конечно прямое произведение в таком случае нифига не поможет, т.к. язык, порождаемый "ca{n}b{n}c" не является регулярным (а прямое произведение регулярных есть регулярный). Почему это так? --- не помню. Вроде когда-то что-то читал про это. Есть какие-то теоремы на этот счет. В любом случае не стоит изобретать вилосипед и лучше ознакомиться с существующей теорией. Ты наверняка сможешь найти что-нибудь полезное и интересное, если попробуешь вылезть в инет.
когда-нибудь да найдём пересечение, если оно естьТебе надо узнать, есть ли пересечение. Ты запускаешь программу, и знаешь - либо она остановится (может, через миллион лет) - значит, пересечение есть. А если она ещё не остановилась - значит, либо ещё не нашла пересечение, либо пересечения нет. Тебе не кажется, что это - не решение?
а тебе не кажется, что прежде чем решать задачу, надо её сформулировать?
это не решение. это утверждение. верное.
это не решение. это утверждение. верное.
А разве в первом посте этого тред задача не сформулирована?
в том виде в котором она сформулирована в первом посте уже был предложен способ решения, который находит ответ за N*M операций (перемножение автоматов).
плюс ко всему то требование, которое ты выдвинул к алгоритму там не изложено.
Я не выдвигал никакого требования. По условию задачи, мы должны узнать, существует ли строка, то есть, получить на выходе либо ДА, либо НЕТ. Твой же вариант будет выдавать только ДА, и мы лишь сможем гадать - "если компьютер долго не говорит ДА, то, может быть, ответ - НЕТ".
согласен
Пацаны, всё гораздо проще
#Unfortunately can't be sure in syntax
#!/usr/local/bin/perl
$#ARGV == 1 or die "Usage>proga <regexp1> <regexp2>";
return 1 if ( $ARGV[0] ~~=~~ $ARGV[1]);
return 0;
Надо письмо написать Лари Волу, чтобы добавил новую операцию, что ему, сложно
#Unfortunately can't be sure in syntax
#!/usr/local/bin/perl
$#ARGV == 1 or die "Usage>proga <regexp1> <regexp2>";
return 1 if ( $ARGV[0] ~~=~~ $ARGV[1]);
return 0;
Надо письмо написать Лари Волу, чтобы добавил новую операцию, что ему, сложно
> язык, порождаемый "ca{n}b{n}c" не является регулярным
Друзья, определитесь пожалуйста, вы имеете в виду регекс "ca{n}b{n}c" при фиксированном n(регулярный) или счётное объединение всех языков, порождаемых при n = 0..+inf (нерегулярный по лемме о накачке, на пальцах так: если у него всего N состояний, то когда мы ему скормим N+1 буковку a, по пути мы встретим два одинаковых состояния с разной длиной префикса (пусть будет m и k тогда на ca{m}b{m}c и на ca{k}b{m}c он выдаст одинаковый результат)?
Я просто как-то перестал понимать, что пытается сказать rott
Друзья, определитесь пожалуйста, вы имеете в виду регекс "ca{n}b{n}c" при фиксированном n(регулярный) или счётное объединение всех языков, порождаемых при n = 0..+inf (нерегулярный по лемме о накачке, на пальцах так: если у него всего N состояний, то когда мы ему скормим N+1 буковку a, по пути мы встретим два одинаковых состояния с разной длиной префикса (пусть будет m и k тогда на ca{m}b{m}c и на ca{k}b{m}c он выдаст одинаковый результат)?
Я просто как-то перестал понимать, что пытается сказать rott
А Е!
Формулирую задачу: есть два контекстно-свободных языка (подпатченные регекспы как минимум КС выяснить, пусто ли их пересечение. КС-языки эквивалентны стековым (ака магазинным) автоматам. Строим двухмагазинный автомат по тем же правилам, по которым мы строили автомат для нахождения пересечения регулярных языков. Наша задача эквивалентна задаче об останове такого автомата (существует ли такое слово, на котором он остановится) (ну да, в обе стороны).
А двухмагазинный автомат эквивалентен машыне Тьюринга.
Ответ: задача о нахождении пересечения двух КС-языков алгоритмически неразрешима.
Я нигде не ошибся? Я не уверен, что у меня в голове именно формальное описание магазинного автомата =(
Формулирую задачу: есть два контекстно-свободных языка (подпатченные регекспы как минимум КС выяснить, пусто ли их пересечение. КС-языки эквивалентны стековым (ака магазинным) автоматам. Строим двухмагазинный автомат по тем же правилам, по которым мы строили автомат для нахождения пересечения регулярных языков. Наша задача эквивалентна задаче об останове такого автомата (существует ли такое слово, на котором он остановится) (ну да, в обе стороны).
А двухмагазинный автомат эквивалентен машыне Тьюринга.
Ответ: задача о нахождении пересечения двух КС-языков алгоритмически неразрешима.
Я нигде не ошибся? Я не уверен, что у меня в голове именно формальное описание магазинного автомата =(
Это:
Просто rott уже перешел от регулярных выражений к некоторому другому множеству выражений, которые порождают уже не только регулярные языки, но и еще какие-то.
счётное объединение всех языков, порождаемых при n = 0..+infда, речь была о нем и он не регулярный. Просто лемм всяких не помню уже, иначе бы сказал про них.
Просто rott уже перешел от регулярных выражений к некоторому другому множеству выражений, которые порождают уже не только регулярные языки, но и еще какие-то.
Формулирую задачу: есть два контекстно-свободных языка (подпатченные регекспы как минимум КС выяснить, пусто ли их пересечение. КС-языки эквивалентны стековым (ака магазинным) автоматам. Строим двухмагазинный автомат по тем же правилам, по которым мы строили автомат для нахождения пересечения регулярных языков. Наша задача эквивалентна задаче об останове такого автомата (существует ли такое слово, на котором он остановится) (ну да, в обе стороны).Не верю про переход от машины Тьюринга к Пересечению двух языков.
А двухмагазинный автомат эквивалентен машыне Тьюринга.
Ответ: задача о нахождении пересечения двух КС-языков алгоритмически неразрешима.
Я нигде не ошибся? Я не уверен, что у меня в голове именно формальное описание магазинного автомата =(
Точно также можно поставить задачу про пересечение регулярных языков, сказать что решается машиной тьюринга, и следовательно неразрешима.
Ну, нужно ещё показать, что мы можем построить практически произвольный двухмагазинный автомат (точнее, эквивалентный произвольному) как произведение двух произвольных одномагазинных. Я в этом практически уверен, проверять влом.
Оставить комментарий
tapo4ek
Такая задача:Есть два регулярных выражения. Требуется определить существует ли строка которая подходит к обоим выражениям.
Есть ли у неё решение и насколько реально его быстро реализовать на языке высокого уровня Java.
P.S. Может кто-нибудь знает что делает ф-я matchesPrefix(...) из jakarta oro