Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Prove the following theorem.
Theorem For any k > 0 and alphabet Σ, the language of all strings over Σ of length k is accepted by a nondeterministic finite automaton.
Note 1: I'm asking for a full proof here. That means you have to provide the whole algorithm, not just the specification!
Note 2: This should be simple. Don't make it tricky, and make sure it's short and sweet.

Problem 2

You're probably (I hope) reasonably convinced from the lecture notes that the language L = {akbk | 0 ≤ k} cannot be accepted by a finite automaton, despite the lack of a true proof. How about the language L' = {akbk%2 | 0 ≤ k} where "k%2" means means "k modulo 2"? Is there an NDFA that accepts this? Prove your answer!