Мне недавно нужно было выяснить правильное выражение для языка {w | | w | нечетно и w начинается и заканчивается символом b} над алфавитом {a, b}.Упрощение регулярного выражения, теория автоматов
я понял, решение будучи
b(ab+bb+aaab+aabb+abab+abbb+bbbb+bbab+babb+baab)*
Раствор очень долго, так что я надеялся, что кто-то может сказать мне, как это может быть упрощенным,
Вы можете попробовать b|(b(a|b)((a|b)(a|b))*b) язык вы описать может производить только b, и это захватывается первой ветвью, и это единственная строка размера 1, которую она может произвести. Тогда он может производить размер 3,5,7, ... строки. Они захватываются второй ветвью. B в начале и в конце не требуют пояснений. И на них приходится 2 символа. Средний бит - классический язык {w | |w| is odd} над {a,b}.
Более мощный синтаксис позволит сделать что-то вроде b((a|b)((a|b)^2)*b)?, что более компактно, но эквивалентно.
Спасибо, хорошее объяснение. –
Самый простой:
(b(a|b)(aa|ab|ba|bb)*b)|b
Ваше "решение" является неправильным. Ловит 'baa', которого нет на вашем языке. В любом случае, если у вас есть больше регулярных выражений, не стесняйтесь призывать мое внимание в комментарии. Я буду рад помочь. – xenteros
Спасибо, на самом деле это была опечатка. Он должен был быть «bb» –
В любом случае, верните правильный ответ, просто чтобы быть справедливым. – xenteros