Регулярное выражение, совпадающее с нечетным числом B с A между (от DFS до Regex)

Question

Предположим, у меня есть детерминированный автомат конечного состояния, который распознает язык L, состоящий из всех строк в {a, b} *, которые содержат нечетное число b, такое, что между каждыми двумя b в строке есть хотя бы один a.

Мне удалось вывести для этого конечный автомат, как показано в этом примере (флажки означают принятое состояние):

Но теперь я застрял;как я могу преобразовать это в регулярное выражение?Я действительно борюсь с этим, так как это довольно сложный пример.Я попытался:

a*b[a*ba*b]*a*

Но это все равно сопоставляет строки с четным числом b.Какое правильное регулярное выражение?

Answer 1

Вы можете использовать

^a*b(?:(?:a+b){2})*a*$

https://regex101.com/r/bSpZ40/2

На обычном языке:

• ноль или более a с, затем следует:

• a b, за которым следует любое количество повторений следующей группы:

  • (хотя бы один a, за которым следует b) повторяется дважды (обеспечивает общее число b с нечетным)

• , за которым следует ноль или более a s

Таким образом, может быть один b, или три b с, или пять b с и т. Д., Каждый b должен иметь некоторое количество a с между ними, и может быть ведущий и /или трейлинг a с.