3
$\begingroup$

I am trying to find the regular expression of this automata using the Arden's Lemma:

enter image description here

Let $L_{i}$ be the language accepted from the state $i$, this is what I got:

  • $L_{1} = 1^{*}0L_{2}$
  • $L_{2} = 1L_{1} + 0L_{3}$
  • $L_{3} = \epsilon + 0^{*}1L_{2}$

As the first state is the initial one, I have to solve $L_{1}$. As $L_{1}$ is expressed using $L_{2}$, I have to first solve $L_{2}$.

$L_{2} = 1(1^{*}0L_{2})+0(\epsilon + 0^{*}1L_{2}) \\ L_{2}=11^{*}0L_{2} + 0\epsilon + 00^{*}1L_{2} \\ L_{2}=(11^{*}0+00^{*}1)L_{2} + 0$

Using Arden's Lemma, I get $L_{2}=(11^{*}0+00^{*}1)^{*}0$

Thus we have now:

$L_{1}=1^{*}0L_{2}=1^{*}0((11^{*}0+00^{*}1)^{*}0)$

Yet, based on this expression, the word "000" isn't accepted. Where is my issues?

$\endgroup$

1 Answer 1

2
$\begingroup$

The mistake is in the equation for $L_3$: it should be $0^*$ instead of $\epsilon$.

$\endgroup$
5
  • $\begingroup$ You mean it should be $0^{*} + 0^{*}1L_{2}$? Why doesn't $\epsilon$ fit there? $\endgroup$
    – John Mayne
    Commented Oct 22, 2016 at 19:14
  • $\begingroup$ That's right. You figure out why $0^*$ should replace $\epsilon$. $\endgroup$ Commented Oct 22, 2016 at 20:54
  • $\begingroup$ Sorry for my last comment, I forgot to add the '$' symbole somewhere, and I am unable to edit it nor delete it. I was writing: I know that $0^{0}=\epsilon$, So putting an epsilon becomes repetitive. I just don't seem to understand why would this ruin my regular expression for the whole automata? $\endgroup$
    – John Mayne
    Commented Oct 22, 2016 at 21:13
  • 1
    $\begingroup$ The formula you state for $L_3$ is just wrong. According to your formula, $0 \notin L_3$, whereas clearly $0 \in L_3$. So your formula is wrong. Your "rule of thumb" is correct inasmuch $0^*$ includes $\epsilon$; but you should be using a rule of thumb but rather something more reliable, a formula that works in all cases, not just most cases (which is what rules of thumb are about). In mathematics our statements should cover absolutely all cases. $\endgroup$ Commented Oct 22, 2016 at 21:56
  • $\begingroup$ @JohnMayne You didn't ruin the whole regular expression, you just forbid the automaton to stop at any time except immediately after entering the state III. As soon as the first 0 transition is done it just has to do a finite number of them and then go to II without a second chance of escaping. Much like if it was $L_3 = \epsilon + 0L_4 + 1L_2$, $L_4 = 0^\ast1L_2$. So by using an $\epsilon$ instead of an $0^\ast$ you created another valid automaton which, exactly as you found, does not accept 000. Disclaimer: not a CSientist. $\endgroup$
    – The Vee
    Commented Oct 23, 2016 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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