1) We want to write a program that will be given a string that contains only the letters from {a,b,c} and that will output yes or no, telling whether the string matches the regular expression a*b|a

a) Draw a deterministic finite automaton that corresponds to the regular expression. Label its states. (Remember to show the initial state and indicate the accepting state(s).)

b) Write a boolean function (Java or pseudocode) that is passed a string that contains only the letters a,b,c, and that returns true if and only if the string matches the regular expression a*b|a

Your function MUST be based on your DFA above (even if your DFA is wrong) and use a variable named state that uses the labels on your DFA. (You can put the transition logic into ifelse or switch if you wish, or in an array).Of course, you cannot use any Java Regex library functions.

2) An elevator is located in a building with 3 floors. It has 5 buttons: a close-door button, an open-door button, and 3 numbered buttons, 1, 2, and 3. When a button is pressed, the elevator does the command (1,2,or 3 button moves the elevator to that floor).

It is not possible to push a button until the previous command has completed. Illegal button presses are ignored. It is illegal to push a numbered button unless the elevator door is closed.

Draw a state machine to model the elevator. Make it easy to understand by giving its states good names and labelling transitions clearly. Do not make it a skeletal diagram (even illegal commands should be shown). .

3) a) Just as an example of a problem, the IsPrime Problem is: given any integer, determine true or false indicating whether or not the given number is a prime number.

Carefully state the Halting Problem.

b) Carefully state what we know about computations that solve the Halting Problem.

c) Explain the cardinality argument that tells us that there are significant limits to what can be computed.

4) a) Construct a regular expression or a finite automaton or a context-free grammar or a pushdown automaton that describes the language of even palindromes using the alphabet {a,b,c}. For example, caabbaac YES, aabaa NO, abcabc NO

b) Using the alphabet {a,b,c} give a Turing Machine (either transition, or composite but not a combination) that decides whether or not an input string contains at least 2 adjacent identical letters. (For example, abacbab NO, abbabc YES). The precondition is the usual one for language recognition |delta alpha...alpha delta .... with the TM starting at the left end). Carefully describe the postcondition for your machine