relation on Languages of one finite machine !?

Question

I adopted this question from 2013 Final Entrance Exam on CS.

We have Finite Machine $M$ and Languages $L_1$ to $L_4$ as depicted in following picture:

Image

The question is which of the $A$ to $D$ is correct?

The short answer sheet says $C$ is correct. Anyone could describe how this will be reached?

Answer 1

It's pretty clear from inspecting the DFA that $L_3 = L(M)$: from $q_0$ we do some sequence of 0ドル$-selftransitions (going throught the loop), and then we must see a 1ドル$ to go to $q_1,ドル which is the only terminating state. We could stop then (so then we just have 0ドル^\ast 1$ as the input sequence), or we do excursions to $q_0$ or $q_2,ドル and so we either have 00ドル^\ast 1$ (if we go to $q_0$ and back, maybe taking some loops in-between) or 10ドル$ if we go to $q_2$ and straight back again. Because we can take as many of these "excursions" as we like, and they're disjoint, we get the extra term $(10 + 00^\ast 1)^\ast,ドル giving us exactly $L_3,ドル which is what I would do first (i.e. determine in my own way what the accepted language is, using this kind of reasoning).

Let's look at $L_1$ which is described by 0ドル^\ast 1 (10)^\ast (00^\ast 1 (10)^\ast)^\ast$. If you follow the automaton we get the same 0ドル^\ast 1$ at the start, to get to $q_1$. Then you get optional excursions to $q_2,ドル and then some optional part that can be described as "1 excursion to $q_0$ followed by any number of excursions to $q_2$", and this part can be repeated as many times as we like.

So if we denote an excursion to $q_0$ by $A,ドル and to $q_2$ by $B,ドル then an accepted sequence, after the initial 0ドル^\ast 1$ is of the form $B^\ast (AB^\ast)^\ast$ which is equivalent to $(A + B)^\ast,ドル i.e. any sequence of $A$'s or $B$'s: such a sequence has a certain number $A$'s: if none, we just have $B^\ast,ドル otherwise we start with a number of $B's,ドル and we use one term $A B^\ast$ for every $A$ we encounter. So in fact $L_1 = L_3 = L(M),ドル which rules out option A.

Now both options B and D claim that $L_4$ also describes the DFA. So look at $L_4,ドル which is described by the regular expression: 0ドル^\ast (1 (10)^\ast 0)^\ast 1 (10)^\ast$. So again, any number of $q_0$-loops at the start. Then an expression that goes to $q_1,ドル does any number of excursions to $q_2$ and goes back to $q_0$. We can do the latter any number of times, including never. Then we do a 1ドル,ドル (so we're back at $q_1$) and do any number of excursions to $q_2$ again, and then stop. So all these strings are accepted by the DFA, so certainly $L_4 \subseteq L(M),ドル and this subset is proper, because in $L_4$ we cannot have long strings of 0ドル$'s in later visits to $q_0$: it's not too hard to see that after the initial 0ドル$'s from 0ドル^\ast$ we can never have 3 or more 0ドル's$ in a row. So e.g. the string 100000001ドル \in L(M)$ but not in $L_4$ so the inclusion is proper, $L_4 \subset L(M)$. This shows that option C is correct already. B and D were already out, as $L(M) \neq L_1$ as we saw.

• Michle Niaye: Very useful. I reading .....