General comment: Unless explicitly specified, each homework should be turned in on a sheet of paper: draw an automaton like we did in class and like the book does, do whatever else needed, add your name on top and turn it in by the beginning of the class on the day when the homework is due.

1. (Due September 6) A recommended name for a class in Java should start with a capital letter, and have only letters (small or capital), digits, and an underscore symbol _. Design an automaton that recognizes such names, and check it on two examples:

• a recommended Java class name, and
• a sequence of symbols which is not a recommended Java class name.

2. (Due September 6) Use the algorithm that we learned in class, with pairs of states from two automata as states of the new deterministic automaton, to design 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₁, 1 leads us to a₂, any other symbol (0, +, 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 b₂.
  • From b₂, 0 or 1 lead us back to b₂, any other symbol (+ or −) leads to the sink.

3. (Due September 13) Use the algorithm that we learned in class to design a non-deterministic automaton recognizing the language (a U b)^*(a U b):

• start with non-deterministic automata recognizing a and b; for example, a non-deterministic automaton recognizing a has two states, the start state and the final state, and the only transition is that when we are in the start state, a 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 a U b;
• apply the general algorithm for the Kleene star to your automaton recognizing a U b, and come up with an automaton that recognizes the language (a U b)^*;
• apply the general algorithm for the concatenation to your automata recognizing (a U b)^* and a U b, and get an automaton recognizing the language (a U b)^*(a U b).

4. (Due September 20) Use the general algorithm to transform the non-deterministic automaton from Problem 3 into a deterministic one.

5. (Due September 20) Write a method that emulates a general finite automaton. The input to this method should include:

• the number N of states q₀, ..., q_{N − 1}; we assume that q₀ is the start state;
• the number M of symbols s₀, ... s_{M − 1};
• an integer array state[n][m] that describes to what state the finite automaton moves if it was in the state q_n and sees the symbol s_m;
• a boolean array final[n] that tells us, for each state, whether this state is final or not.

Your program should emulate the work of the finite automaton 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.

6. (Due September 27) Apply the general algorithm for transforming the finite automaton into a regular language to Automaton B from Problem 2.

7. (Due September 27) Automaton B from Problem 2 accepts the word +010.

• 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 words xyyz and xyyyz are also accepted by this automaton.

8. (Due October 4, due September 27 for extra credit) Prove that the following language is not regular {0ⁿ1ⁿ2ⁿ} = {Λ, 012, 001122, 000111222, ...}.

9. (Due October 18) 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:
  • ε, $ → ε.

10. (Due October 18) The following context-free grammar (CFG) generates palindromes. This CFG has the following rules:

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

11. (Due October 18) 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 +010 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.

12. (Due October 25, extra credit if turned in on October 18) Apply, step-by-step, the general algorithm for transforming a context-free grammar into Chomsky normal form to the context-free grammar from Problem 10 (limit yourselves to only two letters a and b).

13. (Due October 25) Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to the context-free grammar from Problem 10.

14. (Due November 1) Apply, step-by-step, the general algorithm of converting a pushdown automaton to a context-free grammar to the pushdown automaton from Problem 9. Explain how the acceptance of the word abba by this automaton will be translated into a derivation of this word in the resulting grammar.

15. (Due November 1) 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.

16. (Due November 8) 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 November 8) Illustrate the pumping lemma for context-free grammars by showing how it will represent the word s = acb which is generated by the CFG with starting variable S and rules A → ε, S → AS, S → SB, A → a, B → b, and S → c, as uvxyz. Show, step-by-step, how the corresponding word uvvxyyz can be derived from this CFG.

18. (Due November 15) Prove that the language of all the words that have equal number of a's, b's, and c's is not context-free.

19. (Due November 15) Design a Turing machine that, given a positive unary number n, subtracts 1 from this number. Test it, step-by-step, on some example.

20. (Due November 15) Design a Turing machine that, given a positive binary number n, subtracts 1 from this number. Test it, step-by-step, on some example.

21. (Due November 15) 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.

22. (Due November 22) 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.

23. (Due November 22) Give two examples:

• an example of an computation time which makes an algorithm feasible according to the formal definition but not practically feasible, and
• an example of a computation time for which the corresponding algorithm is practically feasible, but not feasible according to the formal definition.

24. (Due November 22) What is NP? What is P? What is NP-complete? What is NP-hard? Give brief definitions. Give an example of an NP-complete problem. Is P equal to NP?

25. (Due November 22, by November 15 for extra credit) As we discussed in class, a Turing machine can be described as a finite automata with two stacks:

• the right stack contains, on top, the symbol to which the head points; below is the next symbol to the right, then the next to next symbol to the right, etc.;
• the left stack contains, on top, the symbol directly to the left of the head (if there is a one), under it is the next symbol to the left, etc.

• how each state of the corresponding Turing machine can be represented in terms of two stacks, and
• how each transition from one state to another can be implemented by push and pop operations.

26. (Due November 22) Apply the general algorithm for transforming a PDA into a 2-tape Turing machine to the PDA that recognizes words of the type aⁿbⁿ. Show, step-by-step, how your Turing machine will accept the word aabb.