If you want to make money online : Register now

Problem using the Arden's Lemma on one automata

, , No Comments
Problem Detail: 

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?

Asked By : John Mayne

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64966

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback