relation on Languages of one finite machine !? 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:


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?
 A: 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.
