Problem 1

The following machine accepts the language of strings over {a,b,c} accepts the language of blocks of aaa and bbb delimited by blocks of one or more c's, with a single a or b following the final c. Transform it into a machine that accepts the strings accepted by the original machine, but with their first character deleted. So, for example, since the original accepts aaacb the new machine should accept aacb. Here's antoher example:

	original accepts: bbbccbbbca
          so new accepts:  bbccbbbca
      

Problem 1.5

Review the concatenation algorithm from the lecture notes, and the proof of correctness there. Part 1 of the proof shows how to take an accepting computation for $M$ on $w$ and turn it into accepting computations for $M_1$ on $u$ and $M_2$ on $v$ where $w = uv$. I want you to follow those directions in the proof and from the below accepting computation for $M$, I want you to write down accepting computations in $M_1$ and $M_2$ that show that $abacbcaa$ is in the concatenation of $L(M_1)$ and $L(M_2)$. I'm not telling you what $M_1$, $M_2$ or $M$ are except that:

• $p$ states come from $M_1$, and $q$ states come from $M_2$

Hint: Look for the $\lambda$-transition taking you from the $M_1$ states to the $M_2$ states!

Problem 2

Prove that if L ⊆ Σ* is accepted by a nondeterministic finite automaton then the language {w ∈ Σ* | there is an x ∈ Σ for which xw ∈ L} is accepted by a nondeterministic finite automaton. In other words, prove that the language of all strings you get by deleting the first character of a string from L is accepted by a nondeterministic finite automaton. Note: this is too hard if the machine M accepting L has λ-transitions coming out of its start state. So assume that this does not occur. We can worry about situations in which it does occur later.