Регулярные выражения.

[max(Im)]

Рассмотрим обычные регулярные выражения (которые эквивалентны КА), правда ли что ими нельзя задать язык строк в алфавите $\{a,b\},$ в каждой из которых подстрока $ab$ встречается столько же раз, сколько $ba$ ?

[Xaositect]

Неправда.
А вот в алфавите $\{a,b,c\}$ задать нельзя.

[max(Im)]

А как это сделать в $\{a,b\}$? Подскажите идею?

[Xaositect]

Подумайте, на сколько могут отличаться количество вхождений $ab$ и $ba$ и в каких случаях.

[max(Im)]

Точно)

Вот так правильно?
$a^+(b^+a^+)^*\, | \,b^+(a^+b^+)^*$

[Xaositect]

Верно. Можно еще так: $(a(a|b)^*a)|(b(a|b)^*b)$