 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/models-of-computation/1/b/i/solution

For

x

, there is an accepting graph path

q_{0} 1 q_{1} 1 q_{2} 0 q_{0} 0 q_{0} 1 q_{1} 1 q_{2} 0 q_{0} ε q_{2} .

Its 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:

Input prefix	Possible automaton states after epsilon closure
$ε$	${q_{0}, q_{2}}$
$1$	${q_{1}}$
$11$	${q_{2}}$
$110$	${q_{0}, q_{2}}$
$1100$	${q_{0}, q_{2}}$
$11001$	${q_{1}}$

The final set contains no accepting automaton state, and

q_{1}

has no outgoing epsilon transition. Therefore $y$ is rejected.

x \in L (M), y \in / L (M) .

 New to topics? Read the docs here!