Please do work on your own - no group work. If you are stuck, contact me. Collaborating on this assignment will be viewed as cheating.
This is an optional assignment: 100 points will be added to your homework score if you get it right. Given you have been doing lots of Java programming recently, I decided you might like a break. So this assignment asks you to think back to Finite Automata and Turing Machines.
Part a. Assume I give you the language described by (xy)*x. First, draw the Finite Automata that accepts just this language. You might want to check with me that you have this right before preceding on to the next part.
Part b. Use the Turing machine simulator from assignment 3 to build the equivalent TM. That is, I want a TM that will accept the language (xy)*x. You can assume that the TM tape starts with any sequence of x's and y's (this is called the sentence). Your TM's job is to determine whether this sentence is in the language.
When your machine halts, it should print a 1 on the tape
if the sentence is in the language and 0 otherwise. As an example,
suppose the tape started with a single y. I would expect your TM
to halt with something like this on the tape:
Turn-in: Your drawn FA from part a, and your xTuringMachine code from part b. I will run your TM code on some test cases to see if it works.
In the end, I hope you can convince yourself that I can turn any FA into a TM. This says that a TM has at least the power of an FA. But we have seen it has even more power. For instance, a TM can recognize palindromes where an FA cannot.