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