Написание регулярного выражения без рекурсивного правила

Question

Мне нужно написать правило регулярного выражения, где выражения, которые у меня есть, не имеют рекурсивного правила.

Например, если мне нужно написать выражение, в котором у меня может быть любое число a, b, c, и d's, но не должно быть никаких a и d's сразу после любых b. a и ds могут появляться позже в строке.

Здесь все правила, которые я могу использовать: Пробовал так: (a|d)* (c|b)* c* (a|d)*. Однако, как вы можете видеть, мне нужно будет продолжать повторять эту работу. Любая помощь будет оценена!

Answer 1

Вам нужно перефразировать вопрос.

У меня может быть любое количество a, b, c и d's, но не имеет никаких а и д, следуя любым b.

Другими словами, вы можете иметь (a|c|d) любое количество раз, но когда если появляется b, то любое число (b|c): так, (a|c|d)* (b (b|c)*) | ɛ).

Формально она равна (a|c|d)* (b|c)* (возможно, вам стоит выяснить, почему), но на практике, несмотря на то, что она короче, эта подвержена катастрофическому сбою при оценке с помощью общих регулярных выражений.

(Если вы хотите, чтобы проверить его на вычислительных/практических регулярных выражений, в отличие от теоретических, это приводит к [acd]*(?:b[bc]*)?.)

EDIT: Да, неправильно вопрос. «сразу после», возможно, был хорошим выбором слов. Как насчет ...

(a|c|d|b+c)*(b|ɛ) 
(?:[acd]|(?:b+c))*b? 

Объясняя логику здесь, вы можете использовать любого из букв, но если вы используете b, вы можете идти с любым количеством b с, но когда вы устаете, что следующей должен быть c (единственный оставшийся, если вы остановили b -инг и не можете сделать a или c). Затем он возвращается к обычной программе. В конце вы можете иметь b, за которым не обязательно следует что-либо.

Answer 2

Вы можете создавать автоматы и преобразовывать их в регулярное выражение. Поскольку и d не может быть после того, как б:

И вот только сказал acd и b принимаются. START также может быть принят, если вы принимаете пустое слово.

Таким образом, вы можете начать использовать с (a|c|d). Он может повторяться без изменения состояния, поэтому (a|c|d)*. Из состояния b вы можете пойти с b* ИЛИ один c - это дает b*|c ->(b(b*|c)). Это дает всего (((a|c|d)*)|(b(b*|c)))*