Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 1 / b

For $x$, there is an accepting graph pathIts nonempty labels spell $1100110$, and its last automaton state is accepting. Therefore $x$ is accepted. The last epsilon transition matters: finishing the consumed input at $q_0$ does not prevent a subsequent move to $q_2$.

For $y$, track all possible automaton states, including their epsilon closure, after each input prefix:

The final set contains no accepting automaton state, and $q_1$ has no outgoing epsilon transition. Therefore $y$ is rejected.

Use state elimination for finite automata, with regular expression labels on a generalized finite automaton. Add a fresh initial automaton state $s$ with $s\stackrel{\epsilon }{\to }{q}_0$, and a fresh final automaton state $f$ with $q_2\stackrel{\epsilon }{\to }f$. Only $f$ is now accepting. Missing labels represent the empty language, and parallel alternatives are combined by union.

When eliminating an internal automaton state $k$, update every surviving label byThe added regular expression describes entering $k$, traversing its loop zero or more times by Kleene star, and leaving it. This accounts for exactly the graph paths newly bypassing $k$.

First eliminate $q_1$. Its only incoming and outgoing labels are both $1$, and it has no loop. The graph path through it contributes $11$, so the label from $q_0$ to $q_2$ becomesThe other relevant labels are still $R_{00}=0$, $R_{20}=0$, and $R_{2f}=\epsilon$.

Next eliminate $q_2$. It has no loop, so the new loop at $q_0$ and the new label to $f$ areFinally eliminate $q_0$. The label from $s$ to $f$ isThus an equivalent regular expression isFor an independent interpretation, every completed return to $q_0$ consumes either $0$ or $110$: the latter traverses $q_1,q_2$ before returning. The last visit to $q_2$ consumes either nothing or $11$. Consequently every run of ones has length exactly two, and successive such runs require at least one zero between them. In particular, consecutive copies of $11$ without a separating zero are not accepted.