Name: ____________________________________________________ Alpha: _____________________

## 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 ⇒*.
• Input: bbabba
• Input: ababbaab

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