Дайте регулярное выражение над Σ = {a,b}...?

Question

Вопрос просит дать регулярное выражение над Σ = {a,b} в формальном представлении (не java), которое генерирует следующие языки:

1. L1 = {x | x содержит подстроку abab}
2. L2 = {x | x имеет нечетную длину}
3. L3 = {x | x не заканчивается в ab}

Я понятия не имею, как написать регулярное выражение. Каковы будут ответы, и если бы вы могли объяснить, почему я был бы чрезвычайно благодарен.

Answer 1

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

1. Σ * · ABAB · Σ *
2. a · {aa, bb, ab, ba} * \cup b · {aa, bb, ab, ba} *
3. Σ * · {bb, a} \cup {b, \ lambda}

где \cup установлен union/OR, а \ lambda - пустая строка.