для простоты, предположим что алфавит у нас из 2х символом a и b (в «настоящих» регулярках это b есть «все кроме a»), тогда (ab | bb)*(a|b|epsilon) есть решение (я использую классическое определение регулярного выражения)
что любое слово из определения входит в наш язык и наоборот любое слово в нашем языке подходит под определение, доказать можно просто по (сильной) индукции по длине слова (в шаге индукции нужно лишь рассматривать отдельно случаи четной и нечетной длины)
на языке «программистских» регулярок получится что-то типа /^((a|[^a])[^a])*(a|[^a])?$/
ну или если упростить («а | [^a]» есть любой символ, т.е. просто "."), то /^(.[^a])*.?$/
на самом деле в таких «заковыристых» случаях вернее всего нарисовать автомат и сконвертить его в регулярку.
на автомате еще и проще доказать будет :)
надеюсь не ошибся нигде ;)
