2
$\begingroup$

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)?

$\endgroup$
2
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ Yes, this is indeed the way which I thought of for solving the odd strings problem (I assume that [ab] in your notation is $(a+b)$ in mine) $\endgroup$ – HaroldF Nov 14 '17 at 10:43
  • $\begingroup$ Sorry, I've adapted my the notation. $\endgroup$ – clemens Nov 14 '17 at 10:53
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You should use $I$ instead of $E$. With a proportional font this should be even shorter than $E$. ;) +scnr+ $\endgroup$ – clemens Nov 14 '17 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.