Regular expression for even/odd string on alphabet

Question

Given the alphabet $\{ a,b \}$, if I want to build the regular expression for even/odd lenght strings, I can think that an even lenght string is given by some combination of $a$'s and $b$'s, and the letters can be paired, so there are four possibilities: $aa,ab,ba,bb$, the regular expression(for even lenght strings) so is:

$(aa+ab+ba+bb)^* $

But can I write this in this other (more compact) way?

(Using, e.g., the notation of Hopcroft-Motwani-Ullman) given a language $L$,

we write $L^i:=\{ w_1w_2...w_i \ \ \ s.t. w_1,w_2,...,w_i \in L \}$

Then given that $(a+b)$ is (as a regular expression) the notation for the strings formed by one symbol, $a$ or $b$, then $(a+b)^2$ as in the notation above is

$\{w_1w_2 \ \ \ s.t. w_1,w_2 \in (a+b)\}=\{aa,ab,ba,bb\}$

So i can rewrite the notation for the regular expression for even lenght words as:

$((a+b)^2)^*$

But this holds in general, so if I want the strings of lenght a multiple on $n \in \mathbb{N}$, I can consider:

$((a+b)^n)^*$

As the regular expression.

I feel like this is somehow cheating and that this argument is not valid, but to me it seems correct: because it is true that exponentiation is not an operation in the language of regular expressions, but it is also true that in reality here exponentiation is only the concatenation $n-$times of the regular expression $(a+b)$, so $(a+b)^2=(a+b)(a+b)$, $(a+b)^3=(a+b)(a+b)(a+b)$, which is always a valid operation for regular expressions.

So my question is: Is the first way in which I have expressed the regular expressions for even-lenght words the most concise way to write it? And if the second way in which I have expressed it is correct, can this be generalised for $n$ generic (as I proposed)?

Answer 1

How about an expression for even strings $((a+b)\cdot(a+b))^*$ and deriving the one for odd strings from it: $((a+b)\cdot(a+b))^*\cdot(a+b)$?

Answer 2

Here is an even shorter regular expression for the set of even length strings: $$ E $$ where I define $E = ((0+1)(0+1))^*$.

The morale is that in order to talk about the shortest regular expression, you have to fix the syntax of regular expressions in advance. If you allow powering in your syntax, then $((0+1)^2)^*$ could be shorter than $((0+1)(0+1))^*$ (whether it is or not depends on how you measure length). If you don't allow powering in your syntax, then $((0+1)^2)^*$ isn't a valid regular expression.

One standard definition of regular expressions over an alphabet $\Sigma$ goes as follows:

• $\epsilon$ and $\emptyset$ are regular expressions.
• For each $\sigma \in \Sigma$, $\sigma$ is a regular expression.
• If $r$ is a regular expression then so is $(r)^*$.
• If $r_1,r_2$ are regular expressions then so are $(r_1+r_2)$ and $(r_1r_2)$.

This defines a language over $\Sigma \cup \{\epsilon,\emptyset,(,),^*,+\}$.

Under this definition, $ab$ is not a regular expression over $\Sigma = \{a,b\}$, since the parentheses are missing. However, in practice we do interpret $ab$ as a regular expression, because we are using a more complicated syntax in which parenthesis are optional and different operators have precedence. Yet in the back of our minds, we interpret $ab$ as the regular expression $(ab)$. Formally, every "relaxed" regular expression has a standard form which does correspond to the specification above, and we often identify the two.

Other syntactic sugar such as powering is treated similarly as a shortcut which helps humans write the regular expression, but is absent when discussing the regular expression formally, for example when measuring its length.