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