1. (Due January 27) Design an automaton that recognizes floating-point real numbers in Java. Show, on two example, how it works: an example of a real number and an example of a string which is not a real number. Reminder: a floating point-real number in Java is a fixed-point real number followed by the letter "e" (small or capital) and an integer; examples: 1.5e3 or −.7e+2.

2. (Due January 27) Design an automaton that accepts only binary strings in which the number of 0s is divisible by 3. For example, your automaton should accept a string 100011, but not a string 00111.

3. (Due January 27) Use a general algorithm that we learned in class to design automata that accept the union and intersection of the following regular languages A and B. The language A is the language of all unsigned binary numbers, as represented by the following finite automaton:

               0,1
              <----
             |     |
      0,1    |     |
-->a1-----> a2---->

• a starting state b1 (which is also final) and
• a state b2.

4. (Due February 1) Use a general algorithm that we learned in class to create a deterministic finite automaton from the following non-deterministic one: we have three states q1, q2, and q3; q1 is the starting state, q1 and q2 are final states.

• From q1, reading 0 or 1 can lead to q2 or to q3.
• from q2, a jump can lead to q3, and from q3, a jump can lead to q1.

5. (Due February 1) For the automata A and B described in Problem 3, use the general algorithm to produce a non-deterministic finite automaton corresponding to concatenation. Then use the genera; algorithm for transforming this non-deterministic finite automaton into a deterministic one.

6. (Due February 1) For the automaton B as described in Problem 3, use the general algorithm to produce a non-deterministic finite automaton corresponding to the Kleene star B^*.

7. (Due February 1) Show, step-by-step, how to form a non-deterministic automaton corresponding to the following regular expression: 0(1^* U 0).

8. (Due February 8) Show, step-by-step, how the general algorithm will produce a regular expression that corresponds to automaton B from Problem 3.

9. (Due February 15) Write a program that simulates a finite automaton based on the user's specification. Your program should ask for:

• the number n of states; the states will be q₁, q₂, ..., q_n; the state q₁ is the starting state;
• ask the user to indicate, one by one, whether each of the states q_i (1 ≤ i ≤ n) is an accept (final) state;
• ask the user for the number s of symbols; symbols will be 0, 1, 2, ..., s − 1;
• for each state and each symbol, ask the user for the number of the next state.

How to submit a program: submit printouts of the code and of the test results. Be prepared to show how the program works if needed.

10. (Due February 15) On an example of an automaton B described in Problem 3, for the word s = 10100, show how to get a decomposition s = xyz described in the Pumping Lemma.

11. (Due February 15) Let L be a language of all expressions consisting of open and close parentheses and of 0s and 1s, in which the number of open curly brackets { is equal to the number of closed curly brackets }. For example, the strings {0} and 1}}0{{1 are in this language, but the string {{0} is not. Prove that this language is not regular.

12. (Due February 15) Describe, step-by-step, how a pushdown automaton for recognizing the language {0ⁿ1ⁿ} -- which is described in the textbook and which we also described in class -- recognizes a sequence 000111.

13. (Due February 22) Use the general algorithm that we learned in class to transform finite automaton A described in Problem 3 into a context-free grammar. Show, step-by-step, how this grammar will generate the word 0111 (which is accepted by the original automaton).

14. (Due February 22) Use the general algorithm to transform the following context-free grammar into a pushdown automaton: S --> 0T1, T --> 0S1, S --> ε, T --> ε. Show, step-by-step, how the word 0011, which is generated by the original context-free grammar as S --> 0T1 --> 00S11 --> 0011, will be accepted by the resulting pushdown automaton.

15. (Due March 2) Copy the correct solution to Problem 5 from the test - as posted on the class website - by hand, in your own handwriting. If you got 10/10 on this problem, you do not need to copy the proof, just turn in a sheet of paper with your name on it and a statement that you got 10/10 on this problem on the test.

16. (Due March 16) Use the general algorithm to transform the following context-free grammar into Chomsky normal form:
S → B
S → bBaB
B → A
A → ε

17. (Due March 21) 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).

18. (Due March 28; extra credit if turned in by March 23) Illustrate the pumping lemma for context-free grammars by showing how it will represent the word s = bbbbaaaa, which is generated by the CFG with rules S --> bBa, B --> bSa, S --> e, as uvxyz. Show, step-by-step, how the corresponding word uvvxyyz can be derived from this CFG.

19. (Due March 28) Use pumping lemma for context-free grammars to prove that the language {a³ⁿb²ⁿcⁿ, n = 0, 1, ...} is not context-free.

20. (Due April 6, extra credit if turned in by April 4) Use a general algorithm that we had in class to design a Turing machine that accepts exactly the words accepted by Automaton B from Problem 3. Illustrate, step-by-step, how it works, on the example of the word 011.

21.(Due April 6, extra credit if turned in by April 4) Design a Turing machine for recognizing the language {aⁿbⁿcⁿ}. This machine should start with the a-section, mark a word a, then go into b-section, mark one of the b-symbols, etc. Illustrate, step-by-step, how it works, on two example: a word aabbcc that belongs to this language, and a word aabc that doesn't belong to the language.

22. (Due April 6, extra credit if turned in by April 4) Design a Turing machine for computing n − 1 in unary code; for n = 0, it should return 0. Trace it on two examples: n = 2 and n = 0.

23. (Due April 13) Write a method that emulates a Turing machine for computing. The input to this method should include:

• the number N of states q₀, ..., q_{N − 1}; we assume that q₀ is a start state, and that the last state q_{N − 1} is a halt 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 written on the tape if the Turing Machine in the state q_n sees the symbol s_m;
• 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.

Example: A Turing machine for adding 1 to a number in unary code has the following rules:

• start, _ --> inNumber, R
• inNumber, 1 --> R
• inNumber, _ --> back, 1, L
• back, 1 --> L
• back, 0 --> halt

• we have N = 4 states: q₀ = start, q₁ = inNumber, q₂ = back, and q₄ = halt;
• we have M = 2 symbols: s₀ = _ 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 --> R means that state[1][1] = 1, symbol[1][1] = 1, and lr[1][1] = R.
• The rule inNumber, _ --> back, 1, L means that state[1][0] = 2, symbol[1][0] = 1, and lr[1][0] = _.
• The rule back, 1 --> L means that state[2][1] = 2, symbol[2][1] = 1, and lr[2][1] = L.
• Finally, the rule back, _ --> halt means that state[2][0] = 3, symbol[2][0] = 0, and lr[2][0] = _.

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

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

• j₀(n) = n;
• 1 is not a valid numerical code of a program;
• j₂(n) = n − 1 for n > 0; j₂(0) = 0;
• j₃(n) = n − 5 for n = 5, 6, ...; for inputs n smaller than 5, the function j₃(n) does not halt;
• j₄(n) = n * n.

25. (Due April 25) Design a Turing machine that adds 2 to a binary number. Trace it step-by-step on the example of n = 2. Show, step-by-step, how the state of the Turing machine can be represented as a finite automaton with two stacks; explain what pop-push operations are needed to go from each state to the next one.

26. (Due April 27) Describe the rules of two Turing machines:

• the first Turing machine computes the function f(n) = n + 1 in unary code;
• the second Turing machine computes the function g(n) = n − 1 in unary code; for n = 0, take g(n) = 0.

27. (Due April 27) The disadvantage of representing a tape as an array -- as in Problem 23 -- is that we have a prior limit on the number of symbols that we need to emulate. A better way to simulate a Turing machine, as we mentioned in class, is to represent the contents of the type as a pair of stacks:

• the first stack represents all the symbols before the head, while
• the second stack represents the symbol at the head's location and all the symbols after that.

Example: Let us show how the Turing machine that adds 1 in unary code is represented as two stacks. We will illustrate it on the example of adding 1 to number 2, i.e., in the unary code, to number 11. We will indicate the location of the head by placing the letter H before and after the symbol at which the head is.

• In the beginning, the head is at the initial blank cell, so the contents of the tape is H_H11. In this case:
  • the first stack is empty, and
  the second stack has _11, with blank _ on top.
• Then, we move one step to the right, the contents of the tape is _H1H1. In this case:
  • the first stack has a blank _, and
  • the second stack has 11.
  To achieve this state, we simulate the movement to the right by popping the blank symbol from the second stack and pushing it into the first stack.
• We move again, now the contents of the tape is _1H1H, so:
  • the first stack has 1_, with 1 on top, and
  • the second stack has 1.
• We move once more, now on tape we have _11H_H, so:
  • the first tape has 11_, and
  • the second tape has _.
• We replace blank with 1, and move left. Now, on tape, we have _1H1H1, so:
  • the first stack has 1_, and
  • the second stack has 11.
  We simulate the movement to the left by popping the blank symbol from the first stack and pushing it into the second stack.
• We move to the left again, we have on tape _H1H11, so:
  • the first stack has _, and
  • the second stack has 111.
• We move once again, now on tape we have H_H111, so:
  • the first stack is empty, and
  • the second stack has 111.