1
$\begingroup$

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

DFA

$\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:

  • 0
    It looks like the rule applies immediately with, for example, $x=x_1$, $\alpha=a$, $\beta=bx_2+\Lambda$?2011-10-09
  • 2
    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?2011-10-09
  • 0
    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.2011-10-09
  • 0
    @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 :(2011-10-10
  • 0
    Actually I agree with Henning Makholm. I tried to understand the DFA and the result is: $x_1 \sim (a^*+b(ab+b)^*(aa)^*)^*$2012-05-09

0 Answers 0