Due:Wednesday, January 20
Face-to-face students: Submit in class.
Online students: submit a scanned or typed homework by email, as an attachment.
Prove that language {ai | i is a perfect square} is not regular. (Hint. If M is a finite state machine that is claimed to solve this language, try running M on inputs of the form a n where n is a perfect square. You will find two such strings a I and a J that take M to the same state, where I = i 2 and J = j 2 for some i and j. Try continuing on a 2i+1.)
Prove that language {ww | w ∈ {a,b}*} is not regular. (A string of a's and b's is in this language if it is some string written twice, such as aabaaaabaa.) (Hint. Suppose that M is a finite machine that is claimed to solve this language. You job is to find a string on which M gives the wrong answer. It suffices to find a string of the form anbamb, where n and m might or might not be the same. Try running M on strings of the form anb.)