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

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) .

 Ancestors (11)

There are no discussions about this article yet.

There are currently no matching articles.