#regex #automata
#регулярное выражение #автоматы
Вопрос:
Пусть {a b} — набор алфавитов, напишите регулярное выражение для:
1) Язык всех тех слов, в которых число a и число b являются нечетными;
2) Язык всех тех слов, длина которых нечетна и которые содержат подстроку ab .
Кроме того, если возможно, пожалуйста, помогите мне найти два разных выражения для каждого, чтобы помочь мне лучше понять, как решать такие проблемы.
Комментарии:
1. Вам нужно предоставить дополнительную информацию о вашем прошлом. Вы видели лемму DFA —> regex reductions или pumping?
2. не уверен, что сказать … впервые изучаю теорию автоматов, сделал немного регулярных выражений… вероятно, я могу привести вам пример того, насколько я могу решить этот вопрос.
3. ответ на первый, a(aa) * b(bb) * b(bb) * a(aa) * … это сгенерирует нечетное число языков a и b, но позиции не будут случайными
4. @user975411: я думаю, цель состоит в том, чтобы позиции были «случайными», то есть произвольными…
Ответ №1:
Для первого есть простой DFA с 4 состояниями, который вы можете создать для распознавания языка. Затем вы можете использовать алгоритм, восстанавливаемый из теоремы Клини (часть, где он говорит, что все языки, распознаваемые FA, генерируются RE), чтобы получить RE, который работает … или просто вывести его из диаграммы.
Для второго вы знаете, что (ab) является частью RE; теперь вам нужно подумать обо всех уникальных способах добавления нечетного числа символов к этому (спереди или сзади) и соединить все эти возможности с для простого и правильного RE .
Я не думаю, что кому-то особенно нравится идея просто дать вам ответ.
Редактировать:
Итак, теперь, когда прошло некоторое время, я проработаю ответ на первый, чтобы показать заинтересованным читателям, как это можно сделать.
Наш первый FA заключается в следующем:
Q s f(Q, s)
-- - -------
EE a OE
EE b EO
OE a EE
OE b OO
EO a OO
EO b EE
OO a EO
OO b OE
Мы удалим состояния из этого и заменим s регулярным выражением, чтобы охватить это состояние. Начнем с простого… давайте избавимся от OE. Вот таблица для этого…
Q regex f(Q, s)
-- ---------------------- -------
EE aa EE
EE ab OO
EE b EO
EO a OO
EO b EE
OO a EO
OO ba EE
OO bb OO
Убедите себя, что это правильно, прежде чем продолжить. Далее мы избавляемся от EO:
Q regex f(Q, s)
-- ---------------------- -------
EE aa bb EE
EE ab ba OO
OO ab ba EE
OO aa bb OO
Чтобы упростить следующий шаг, мы вводим новый начальный набор X и новое принимающее состояние Y; OO больше не принимает. Мы устраняем необходимость в OO:
Q regex f(Q, s)
-- ---------------------------- -------
X empty EE
EE aa bb (ab ba)(aa bb)*(ab ba) EE
EE (ab ba)(aa bb)* Y
Следовательно, конечное регулярное выражение
(aa bb (ab ba)(aa bb)*(ab ba))*(ab ba)(aa bb)*
Мы можем начать пытаться перечислить наименьшие строки, которые это генерирует, просто в качестве базовой проверки работоспособности: {ab, ba, aaab, aaba, bbab, bbba, abaa, abbb, baaa, babb, …} Выглядит хорошо для меня!
Правила сокращения на каждом шаге могут быть формализованы, или вы можете просто применить тщательные рассуждения, чтобы убедиться, что вы получаете правильные вещи. Проверьте доказательство теоремы Клини для тщательного анализа. Кроме того, Введение Мартина в формальные языки или что-то в этом роде содержит хорошие примеры использования этого алгоритма.
Комментарии:
1. да, спасибо… но проблема, с которой я сталкиваюсь, заключается в том, что я не уверен, как рандомизировать, сохраняя это выражение (a (aa) * b (bb) * b (bb) * a(aa) *), которое я сделал согласованным… возможно, мне нужно прочитать больше частей книги, которые я делаю…
2. Можете ли вы создать DFA? Если это так, существует алгоритм для восстановления RE, и вам вообще не нужно думать… просто следуйте инструкциям! Вероятно, в Интернете есть Java-приложение, которое выполняет это преобразование бесплатно.
3. я все еще не могу вывести выражение .. можете ли вы только сказать мне, как нарисовать DFA для нечетного числа символов..
4. Имеют четыре состояния, называемые EE, EO, OE и OO. EE — начальное состояние. OO — единственное принимающее состояние. E означает «четное число до сих пор», O означает «нечетное число до сих пор», первая буква говорит, сколько а, вторая, сколько б. E переходит в O и наоборот для каждой буквы каждый раз, когда вы ее видите.