Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

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