REGEX L (r) = {a ^ nb ^ m: n + m четное}, r =?

Question

Итак, я сделал ранее проблему, которая гласила:

L(r) = {w in {a,b}* : w contains at least 2 a's}

Для этой я сказал {a^2n , b}, потому что это гарантирует строку типа aab или aabaab и т. Д. Не уверен, как подойти кодин я написал в названии.Возможно, решением может быть a^2n, b^2m, поэтому его всегда четно, но также 2 нечетных числа, таких как a^n b^3m, также всегда четны.Могу ли я установить границы как n>=m?

Спасибо!

Answer 1

Вы правильно заметили, что n и m должны быть либо четными, либо нечетными.Нужно только добавить, что нечетное число на единицу больше, чем четное число.

Простое регулярное выражение для "четного числа a s" ({a<sup>2n</sup> : n &ge; 0}) равно (aa)*, тогда как«нечетное число a s» равно (aa)*a.

Основываясь на этом, мы можем два случая для исходного вопроса: (aa)*(bb)* и (aa)*a(bb)*b, которые можно объединить в (aa)*(ab+ε)(bb)*,(Предполагается, что вы используете + для чередования и ε для пустой строки.)