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

Question

Я пытаюсь написать регулярное выражение для языка, состоящего из:

• Строки, которые содержат любое количество элементов а затем один б и
• Строки, которые содержат любое количество of a, за которым следует один b, за которым следует четное число a.

Я думал, (b | ((a^+)b)^*) U (a | ((b^+) a)*), но было неправильно.

Есть ли кто-нибудь, кто знает, где я ошибаюсь?

Answer 1

Успенская

Я предполагаю, что это должно быть "strings that consist of", не "strings which contains". Разница в том, что bbbbbaaabaabbbb будет действительной строкой, если она "contains" (так как она содержит aaabaa).

Чтобы сделать это "strings that contains", единственное отличие будет добавление .*? в начало и .* до конца (или [ab]*? и [ab]* если вы хотите ограничить его a и b).

Анализ проблемы

Я верю, что можно упростить проблему просто "strings that consist of any number of a's followed by a single b followed by an even number of a's", так как 0 является четным числом.

Я понятия не имею, что ^ или U делает в вашем регулярном выражении. Является ли этот язык специфическим синтаксисом (обычно ^ указывает начало строки/строки)?

Решение

Это должно быть так же просто, как:

a*b(aa)* 

a* - любое количество элементов а
b - один б
(aa)* четное число элементов а

EDIT:

Согласно комментариям, кажется, что вы можете захотеть строк, которые состоят из чего-то вроде:

• любое количество элементов а
• следует любое количество следующего:
  • один б
  • , за которым следует четное число (номер!= 0)
• необязательно с последующим аб

Регулярное выражение будет:

a*(b(aa)+)*b?