Имеется ли два произвольных регулярных выражения, существует ли «эффективный» алгоритм для определения того, соответствуют ли они одному и тому же набору строк? В более общем смысле, можем ли мы вычислить размер пересечения двух наборов совпадений? Какие алгоритмы существуют для этого и в каком...
Я знаю, что языки, которые можно определить с помощью регулярных выражений, и языки, распознаваемые DFA / NFA (конечными автоматами), эквивалентны. Также не существует DFA для языка . Но все это можно записать с помощью регулярных выражений (в этом отношении любого нерегулярный язык может быть) ,...
Один из способов рассмотрения регулярных выражений - это конструктивное доказательство следующего факта: можно создавать регулярные языки, начиная с небольшого набора языков и комбинируя их с помощью небольшого фиксированного набора свойств замыкания. В частности, если мы начнем с пустого языка,...
Мы можем сформировать DFA, принимающий двоичные числа, делимые на nnn . Например, DFA, принимающий двоичные числа, делимые на 2, может быть сформирован следующим образом: Аналогично, DFA, принимающий двоичные числа, делимые на 3, может быть сформирован следующим образом: Мы можем следовать четко...
Поскольку я готовлюсь к курсу обучения в колледже формальных языков, я наткнулся на эти увлекательные посты ( Один Два ), в которых описывается, как найти простое число с помощью регулярного выражения . Как я уже сказал, регулярное выражение , а не регулярное выражение . Поскольку регулярное...
Я сдал экзамены по теории вычислений несколько недель назад, и это был один из вопросов: Предположим, что языкL={(anbm)r∣n,m,r≥0}L={(anbm)r∣n,m,r≥0}L=\{(a^nb^m)^r \mid n,m,r\ge 0\} L регулярно? Если да, укажите для него регулярное выражение или автомат. После того, как я кратко спросил его ответ...