Регулярное выражение для языка

Question

Мне нужно найти регулярное выражение, которое описывает язык {w in {a,b,c}* | neither bc nor cb is part of w}.

Я думал об этом так: потому что ни bc, ни cb не могут быть частью регулярного выражения, любая последовательность b, за которой следует последовательность c или наоборот, должна иметь по крайней мере одну «a» перед последовательностью c. Это способ, которым я пришел со следующим раствором:

(a+b)* | (a+c)* | (a+b)*a(a+c)* | ((a+b)*a(a+c)*a)* | (a+c)*a(a+b)* | ((a+c)*a(a+b)*a)* 

Я не уверен в правильности моего решения, и поэтому я думал о выяснении здесь, если он работает. И кроме этого существует математический способ нахождения соответствующего регулярного выражения? Потому что мое решение основано только на интуиции.

Заранее спасибо.

Answer 1

Я думаю, что это можно упростить.

Вы можете иметь либо a s или b s, которые следуют a или b или ничто, или c с, за которыми следуют либо a или c или ничего:

^(a|b([ab]|$)|(c[ac]|$))*$ 

С lookahead assertions, это проще :

^(a|b(?!c)|c(?!b))*$ 

Answer 2

Мы могли бы иметь следующее:

предшествуют ничем,
б предшествуют не с,
с предшествуют не б

Это приводит к:

regex = "^(?:a|(?<!c)b|(?<!b)c)*$" 

^ говорит "начинается с"
a ручками " а затем b или c или ничего, поскольку рекурсия будет обрабатывать то, что происходит после «
(?<!c) говорит:« b следовали за т предшествуют с»
(?<!b) говорит„с последующим, но не предшествует Ъ“
* говорит 0 или больше предыдущего выражения
$ говорит„заканчивается“

Чтобы понять, как это работает, давайте рассмотрим "cb" , «Первая итерация» соответствует третьему термину, где мы просто получаем «c». Итак, у нас осталось 'b'. b переходит ко второму термину, но из-за негативного внешнего вида не удается, и мы не соглашаемся.

EDIT:
Оглядываясь назад, я, вероятно, должен был использоваться lookaheads вместо просмотра назад, но оба пути являются правильными, и это хорошо для вас, чтобы понять несколько способов решения этой проблемы.