3

I'm having trouble trying to find a language expressed by this automation. I have constructed a next-state table to help me understand better. From my understanding, any string that starts with 0 takes my automaton A to an accepting state but what if it doesn't start with 0 i.e a 1? The automation would need 14n to take us back to S0 enter image description here

I want to

  • Find the language accepted by the automaton
  • Find a regular expression that defines the same language
J.-E. Pin
  • 40,163
ekeith
  • 169
  • In addition to my answer notice that not every string starting with a $0$ will be accepted, e.g. $01$. However if you have a string that is already being accepted, it will still be accepted no matter how many $0$s you add anywhere to the string. – Christian Ivicevic Jan 07 '17 at 12:56
  • Doesn't that mean any string starting with 0 would be accepted then? Since you said if it is already being accepted (When its 0 the first time it becomes accepted) it will still be accepted@ChristianIvicevic – ekeith Jan 08 '17 at 10:32
  • No, it does not. Let $w$ be a string that is already being accepted. That means that there is a sequence of states $(s_0,\ldots,s_1,s_2,s_3,s_0)$ which accepts the word. If we prepend a few zeros like $00w$ the sequence will be $(s_0,s_0,s_0,\ldots,s_1,s_2,s_3,s_0)$ hence the new word is still accepted. However the word $v=01$ isn't accepted since the sequence $(s_0,s_1)$ we obtain by reading $v$ does not end in a final state. Prepending zeros won't change that for your specific automaton. – Christian Ivicevic Jan 08 '17 at 11:36
  • In addition to my explanation be careful with the wording and the condition in my first comment. Let $L$ be the language described by the automaton then I claimed that $$w\in L \implies 0w \in L.$$ Prepending zeros will yield more words in $L$ only if the word $w$ was already in $L$. And to add a final remark with regards to my former comment about sequences: while reading a word using an automaton you might enter a final state, however you might leave it soon after! A word is only accepted once you have stopped in a final state after reading the entire word. – Christian Ivicevic Jan 08 '17 at 11:40

2 Answers2

2

Converting NFAs to regular expressions

The theory of this method is very well described on the CS Stack Exchange. I am directly going to apply it since it is so simple in this case that you might follow without knowing the algorithm yet.

I am going to introduce a system of equations to describe the language $S_n$ that is being accepted starting from state $s_n$ with the following equations:

$$\begin{align*}S_0 &\equiv 0S_0~\mid~1S_1~\mid~\epsilon\\ S_1 &\equiv 0S_1~\mid~1S_2\\ S_2 &\equiv 0S_2~\mid~1S_3\\ S_3 &\equiv 0S_3~\mid~1S_0\end{align*}$$

An expression of the form $S_m\equiv aS_n$ represents a transition from $s_m$ to $s_n$ by reading $a$ and the $\epsilon$ marks a state as a final state. We are looking for a final expression for $S_0$ (the language accepted starting from state $s_0$) and need some tricks to get to that point.

Now I am going to use Ardens Lemma which states (written using regular expressions and not sets of languages) that $$X\equiv \alpha X~\mid~\beta\implies X\equiv \alpha^*\beta$$ which helps to solve equations of the the form that is described on the left side. We can apply this to all four rules which yields the following (I am doing this backwards):

$$\begin{align*} S_3 &\equiv 0S_3~\mid~1S_0\color{red}{\equiv 0^*1S_0}\\ S_2 &\equiv 0S_2~\mid~1S_3\color{red}{\equiv 0^*1S_3}\\ S_1 &\equiv 0S_1~\mid~1S_2\color{red}{\equiv 0^*1S_2}\\ S_0 &\equiv 0S_0~\mid~1S_1~\mid~\epsilon\\ &\equiv 0S_0~\mid~(1S_1~\mid~\epsilon)\\ &\;\color{red}{\equiv 0^*(1S_1~\mid~\epsilon)} \end{align*}$$

Now we have to plug in $S_3$ into $S_2$ into $S_1$ into $S_0$:

$$\begin{align*} S_0 &\equiv 0^*(1S_1~\mid~\epsilon) \\ &\equiv 0^*(10^*10^*10^*1S_0~\mid~\epsilon) \\ &\equiv 0^*10^*10^*10^*1S_0~\mid~0^* \\ &\;\color{red}{\equiv(0^*10^*10^*10^*1)^*0^*}. \end{align*}$$

The very last equivalence in red follows from Ardens Lemma once again - just be careful how to handle the expression preceeding it.

My result supports J.-E. Pins solution and disproves Globe Theatres solution as well.

Community
  • 1
Christian Ivicevic
  • 3,123
0

A possible answer is $(0 + 10^*10^*10^*1)^*$. There are other equivalent solutions, but the answer proposed by Globe Theatre does not match for instance $01111$, and hence is incorrect.

J.-E. Pin
  • 40,163
  • My solution is supporting your result as well - this seems to be another representation of the same language. – Christian Ivicevic Jan 07 '17 at 12:45
  • @christian-ivicevic Yes, the two representations are equivalent. More generally, if $r$ and $s$ are regular expressions, $(r + s)^$ and $(r^s)^r^$ are equivalent. – J.-E. Pin Jan 07 '17 at 13:06