1. (Due January 19) Design an automaton that recognizes real numbers in Java (both fixed-point and floating-point ones), and check it on two examples:

• a legitimate Java real number, and
• a sequence of symbols which is not a legitimate real number.

2. (Due January 26) Use the algorithm that we learned on January 19, with pairs of states from two automata as states of the new deterministic automaton, to describe the automata recognizing the union and the intersection of the languages A and B corresponding to the following automata:

• The automaton corresponding to the language A has three states:
  • the starting state a₁,
  • the final state a₂, and
  • a sink state a₃.
  The transitions are as follows:
  • From a₁, 0 leads us to a₂, any other symbol (1, +, or −) leads to the sink.
  • From a₂, any symbol leads to the sink.
• The automaton corresponding to the language B also has three states:
  • the starting state b₁,
  • the final state b₂, and
  • a sink state b₃.
  The transitions are as follows:
  • From b₁, 0 or 1 leads us to b₂, any other symbol (+ or −) leads to the sink.
  • From b₂, 0 or 1 lead us back to b₂, any other symbol (+ or −) leads to the sink.

3. (Due January 26) Use the algorithms that we learned in class on January 24 to design a non-deterministic automaton recognizing the language (0 U 1)(0 U 1)^*:

• start with non-deterministic automata recognizing 0 and 1; for example, a non-deterministic automaton recognizing 0 has two states, the start state and the final state, and the only transition is that when we are in the start state, 0 leads to the final state;
• use the general algorithm for the union of languages represented by non-deterministic automata to design a non-deterministic automaton recognizing the language 0 U 1;
• apply the general algorithm for the Kleene star to your automaton recognizing 0 U 1, and come up with an automaton that recognizes the language (0 U 1)^*;
• apply the general algorithm for the concatenation to your automata recognizing 0 U 1 and (0 U 1)^*, and get an automaton recognizing the language (0 U 1)(0 U 1)^*.

4. (Due February 2) Use the general algorithm that we learned in class to come up with a regular expression that describes all the words accepted by the following automaton:

• This automaton has 3 states, the starting state q₁, and the two final states q₂ and q₃.
• The corresponding alphabet consists of two symbols: a and b.
• When you see a, from q₁ you move to q₂, from q₂ you move to q₃, and from q₃ you move to q₁.
• When you see b, from q₁ you move to q₃, from q₂ you move to q₁, and from q₃ you move to q₂.

5. (Due February 9) Let us consider the following automaton: the automaton from the Problem 4 accepts the following word: aabbaa.

• Trace, step-by-step, that this word is indeed accepted by the given automaton.
• Use this tracing to find the parts x, y, and z of this word corresponding to the Pumping Lemma.
• Trace that the word xyyz is also accepted by this automation.

6. (For extra credit, due February 9) Prove that the following language is not regular {aⁿbⁿcⁿ, n = 0, 1, 2, ...} = {Λ, abc, aabbcc, aaabbbccc, ...}.

7. (Due February 16) In class, we had a pushdown automaton for recognizing words of the type ww^R, where w is any word, and w^R means the same word reversed.

For example, if w = ab, then w^R = ba, and ww^R = abba.

The automaton that we came up with has 4 states:

• the starting state s,
• the reading state r,
• the checking state c, and
• the final state f.

• From s to r, the transition is:
  • ε, ε → $;
• From r to r, the transitions are:
  • a, ε → a;
  • b, ε → b;
  • ...
  for every possible symbol a, b, ...
• From r to c, we have a jump ε, ε → ε.
• From c to c, the transitions are:
  • a, ε → a;
  • b, ε → b;
  • ...
  for every possible symbol a, b, ...
• From c to f, the only transition is:
  • ε, $ → ε.

8. (Due February 16, for extra credit) Modify the pushdown automaton described in Problem 7 so that the new automaton will recognize all palindroms, not only palindroms of the type ww^R. For example, the word madam should be recognized by this palindrom. Show, on an example of a palindrom different from what we had in class, how your automaton will recognize this palindrim.

9. (Due February 16) In class, we considered a context-free grammar (CFG) that generates palindroms. This CFG has the following rules:

• S → ε,
• S → a,
• S → b,
• ...,
• S → z,
• S → aSa,
• S → bSb,
• ...,
• S → zSz.

10. (Due February 23) On the example of the Automaton B from Problem 2, show how the general algorithm will produce a context-free grammar that generates all the words accepted by this automaton -- and only words generated by this automaton. On the example of a word 1011 accepted by this automaton, show how the tracing of acceptance of this word by the finite automaton can be translated into a generation of this same word by your context-free grammar.

11. (Due February 23) Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to the context-free grammar with the following rules:

• S → ε,
• S → d,
• S → o,
• S → r,
• S → dSd,
• S → oSo,
• S → rSr.

12. (Due March 7) Apply, step-by-step, the general algorithm for transforming a context-free grammar into Chomsky normal form to the following context-free grammar. This grammar generates both palindromes composed of letters a and b and words of the type aⁿbⁿ:

• S → P,
• P → ε,
• P → aPa,
• P → bPb,
• S → W,
• W → ε,
• W → aWb.

13. (Due March 2 for extra credit, due March 7 for regular credit) Apply, step-by-step, the general algorithm of converting a pushdown automaton to a context-free grammar to the following pushdown automaton. This pushdown automaton has four states:

• the starting state s,
• the reading state r,
• the checking state c, and
• the final state f.

• From s to r, the transition is:
  • ε, ε → $
• From r to r, the transitions are:
  • a, ε → a
  • b, ε → b
• From r to c, we have a jump:
  • ε, ε → ε
• From c to c, the transitions are:
  • a, a → ε
  • b, b → ε
• From c to f, the only transition is:
  • ε, $ → ε

14. (Due March 9) Show, step by step, how the stack-based algorithm will transform the expression (1 + 2) * (3 − 4) into a postfix expression, and then how a second stack-based algorithm will compute the value of this postfix expression.

15. (Due March 9) Illustrate the pumping lemma for context-free grammars by showing how it will represent the word s = aaacbbb which is generated by the CFG with rules S → ε, S → a, S → b, S → c, S → aSb, S → bSa, and S → cSc, as uvxyz. Show, step-by-step, how the corresponding word uvvxyyz can be derived from this CFG.

16. (Due March 23) Write a program that, given an arithmetic expression,

• first transforms it to a postfix form, and then
• computes its value (by using the stack-based algorithms that we recalled in class).

• as with all programming assignments for this class, submit a printout of the code, and a printout of an example of what this program generates on each step;
• ideally, use Java, but if you want to write it in some other programming language, check with the TA that it is OK; usually, C or C++ are OK.

17. (Due March 23) Design a Turing machine that, given a unary number n, adds 2 to this number. Test it, step-by-step, on some example.

18. (Due March 23) Design a Turing machine that, given a binary number n, adds 2 to this number. Test it, step-by-step, on some example.

19. (Due March 30) Transform a finite automaton B from Problem 2 into a Turing machine. Show step-by-step, on an example of a word 010, how this word will be recognized by your Turing machine.

20. (Due March 30) Write a method that emulates a general Turing machine. The input to this method should include:

• the number N of states q₀, ..., q_{N − 1}; we assume that q₀ is the start state, that the last-but-one state q_{N − 2} is the accept state, and the last state q_{N − 1} is the reject state;
• the number M of symbols s₀, ... s_{M − 1}; we assume that s₀ is the blank state _;
• an integer array state[n][m] that describes to what state the Turing machine moves if it was in the state q_n and sees the symbol s_m;
• an integer array symbol[n][m] that describes what symbol should be on the tape after the Turing Machine in the state q_n sees the symbol s_m (it may be the same symbol as before, or it may be some other symbol written by the Turing machine);
• a character array lr[n][m] that describes, for each state q_n and for each symbol s_m, whether the Turing machine moves to the left (L), or to the right (R), or stays in place (blank symbol);
• the integer array of a large size describing the original contents of the tape, i.e., what symbols are written in each cell.

Your program should emulate the work of the Turing machine step-by-step. Return the printout of the method, the printout of the program that you used to test this method, and the printout of the result of this testing. Feel free to use Java, C, C+++, Fortran, or any programming language in which the code is understandable.

Example: A Turing machine for checking whether a binary string is even (i.e., ends with 0) has the following rules:

• start, _ --> inNumber, R
• inNumber, 1 --> state1, R
• inNumber, _ --> reject
• inNumber, 0 --> state0, R
• state0, 1 --> state1, R
• state0, 0 --> state0, R
• state1, 1 --> state1, R
• state1, 0 --> state0, R
• state1, _ --> reject
• state0, _ --> accept

• we have N = 6 states: q₀ = start, q₁ = inNumber, q₂ = state1, q₃ = state0, q₄ = accept, and q₅ = reject;
• we have M = 3 symbols: s₀ = _, s₁ = 0, and s₂ = 1;

• The first rule start, _ --> inNumber, R means that state[0][0] = 1, symbol[0][0] = 0, and lr[0][0] = R.
• The second rule inNumber, 1 --> state1, R means that state[1][2] = 2, symbol[1][2] = 2, and lr[1][2] = R, etc.

21. (Due April 13) In the proof that the halting problem is not algorithmically solvable, we use a diagonal function
f(n) which was defined as follows:

• f(n) = j_n(n) + 1 if n is a valid code of a Java program and j_n halts on n;
• f(n) = 0 otherwise.

• j₀(n) = 3 * n + 2;
• j₁(n) = n * n; and
• 2 is not a valid numerical code of a program

22. (Due April 20) Not all algorithms are feasible, but, unfortunately, we do not have a perfect definition is feasibility. Give two examples:

• an example of an algorithm which is feasible according to the current definition but not practically feasible, and
• an example of an algorithm which is practically feasible but not feasible according to the current definition.