Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Consider the machine M given by:
( {(p0,q0),(p0,q1),(p1,q0),(p1,q1)}, {a,b},
       |    a       b
-------+----------------
(p0,q0)| (p0,q1) (p1,q0)
(p0,q1)| (p0,q0) (p1,q1)
(p1,q0)| (p1,q1) (p0,q0)
(p1,q1)| (p1,q0) (p0,q1)
, (p0,q0), {(p0,q0),(p1,q0),(p1,q1)} )
Write the sequence of configurations describing the computation of M on input bbabba and on input ababbaab, indicating which are accepting computations and which are rejecting computations. You must show all configurations/steps of the computation, i.e. you must use ⇒ not ⇒*.

Problem 2

Suppose we are given DFA $M = (Q,\Sigma,\delta,s,W)$ and string $w = abcbbabbc \in \Sigma^*$ such that for states $p \in Q$ and $q \in W$ we have \[ (s,abcbbabbc) \Rightarrow^* (p,cbbabbc) \Rightarrow^* (p,abbc) \Rightarrow^* (q,\lambda). \] Prove that $w$ cannot be the longest string in $L(M)$.