Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to create a regular expression from the following deterministic finite automaton using an equivalence system:


$\begin{align}L_1 = & \{a\}L_1 &\cup& \{b\} L_2 & \cup & \Lambda L_3 &\cup&\{\epsilon\} \\ L_2 = & \emptyset L_1 &\cup& \{b\} L_2 & \cup & \{a\} L_3 &\cup&\{\epsilon\} \\ L_3 = & \{a\}L_1 &\cup& \{b\} L_2 & \cup & \Lambda L_3 &\cup&\emptyset\end{align}$

$\begin{align}x_1 \sim & a x_1 &+& b x_2 &+& \Lambda x_3 &+& \Lambda^* \\ x_2 \sim & \Lambda x_1 &+& b x_2 &+& a x_3 &+& \Lambda^*\\ x_3 \sim & a x_1 &+& b x_2 &+& \Lambda x_3 &+& \Lambda\end{align}$

$\begin{align}x_1 \sim & a x_1 &+& b x_2 &+& \Lambda^* \\ x_2 \sim & b x_2 &+& a x_3 &+& \Lambda^*\\ x_3 \sim & a x_1 &+& b x_2 &+& \Lambda\end{align}$

But I don't find any possibility to simplify or to use the resolution rule $$\text{let } \alpha,\beta \in RE(\Sigma). \;\; x \sim \alpha x + \beta \wedge \epsilon \not\in [[\alpha]] \Rightarrow x \sim \alpha^*\beta$$ with $RE(\Sigma)$ being the set of regular expressions on the alphabet $\Sigma$.

The final result should be $x_1 \sim ?$ with $?$ containing no other $x_i$.

Do you have any idea what my mistake might be or what next step I don't see?

Thanks in advance!

[Edit] Just a working example clarify the desired way of solving thisenter image description here:

share|cite|improve this question
It looks like the rule applies immediately with, for example, $x=x_1$, $\alpha=a$, $\beta=bx_2+\Lambda$? – Henning Makholm Oct 9 '11 at 22:05
By the way, you do know that the systematic approach will probably lead to a rather unwieldy expression compared to trying to understand what the DFA does and then just write down something like $\varepsilon+a+(a+b)^*(aa+b)$, right? – Henning Makholm Oct 9 '11 at 22:09
Also, it looks incorrect that you're using $\Lambda$ in the expressions for $L_1$ and $L_3$ in places where I would have expected $\emptyset$, like in your $L_2$ expression. In your regular expressions it seems that you're using "$\Lambda$" as an expression that matches no strings at all -- are you sure that is how it works in the formalism you're using? Most often people use $\Lambda$ to denote the empty word, so when it appears in a regular expression one would expect it to match the empty string, rather than not matching anything. – Henning Makholm Oct 9 '11 at 22:18
@HenningMakholm I added an example of how this should work ;) $\Lambda$ is not the empty word but the empty set (?) so it should just be as you proposed. I know there are better, faster and more elegant ways for finding the desired expression but unfortunately I need to practise this one :( – muffel Oct 10 '11 at 14:42
Actually I agree with Henning Makholm. I tried to understand the DFA and the result is: $x_1 \sim (a^*+b(ab+b)^*(aa)^*)^*$ – Ehsan May 9 '12 at 9:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.