## Automata, Homeworks for the course CS 3350, Fall 2015

1. (Due September 2) 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 September 2) Design an automaton that accepts only binary strings in which the number of 1s is divisible by 4. For example, your automaton should accept a string 11011, but not a string 00111.

3. (Due September 9) 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---->
```
In this automaton A, only a2 is a final state. The language B is the language of all binary sequences that have odd number of 1s. This automaton has two states:
• a starting non-final state b1 and
• a final state b2.

4. (Due September 9) Use a general algorithm to create a deterministic finite automaton corresponding to the following non-deterministic one: we have three states q1, q2, and q3, q1 is the staring state, q2 is the only final state.

• 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 q2.

5. (Due September 16) For the automaton A as described in Problem 3, use the general algorithm to produce a non-deterministic finite automaton corresponding to the Kleene star A*. Then use the general algorithm for transforming this non-deterministic finite automaton into a deterministic one.

6. (Due September 16) Use a general algorithm to describe a regular expression corresponding to the automaton A from Problem 3.

7. (Due September 23) Write a program that would simulate a finite automaton based on the user's specification. Your program should ask for:

• the number n of states; the states will be q1, q2, ..., qn; the state q1 is the starting state;
• ask the user to indicate, one by one, whether each of the states qi (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.
Store the set of accept states in a boolean array accept of size n, and the next states in a 2-D array next. Once the automaton is formed, your program should be able to check whether a given string of digits is accepted by this automaton.

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.

8. (Due date September 23) Prove that the square root of 15 is irrational.

9. (Due date September 23) Prove, by induction, that 1 + 3 + 5 + ... + (2n − 1) = n2.

10. (Due date September 30) On an example of an automaton described in Problem 3, for any sufficiently long sequence of symbols s accepted by this automaton, show how to get a decomposition s = xyz described in the Pumping Lemma.

11. (Due date September 30) Let L be a language of all expressions consisting of open and close parentheses, in which the number of open parentheses is equal to the number of closed parentheses. For example, the strings () and ))(( are in this language, but the string (() is not. Prove that this language is not regular.

12. (Due date October 7) Describe, step-by-step, how a pushdown automaton for recognizing the language {0n1n} -- which is described in the textbook -- recognizes a sequence 00001111.

13. (Due date October 7) Describe, step-by-step, how a pushdown automaton for recognizing the language {wwR} -- which is described in the textbook -- recognizes a sequence 010010.

14. (Due date October 7) Transform a finite automaton A from Problem 3 into a context-free grammar.

15. (Due date October 14) Use a general algorithm to transform the following grammar to Chomsky normal form:
S --> A
S --> aAbA
A --> B
B --> ε

16. (Due date October 21) Use a general algorithm to construct a pushdown automaton that recognizes the grammar described in Problem 15.

17. (Due date October 21) Use a general algorithm to construct a context-free grammar corresponding to the {0n1n}-recognizing pushdown automaton described in the textbook.

18. (Due date October 28) Illustrate the pumping lemma by showing how it will represent the word s = aaaabbbb, which is generated by the CFG with rules S --> aAb, A --> aSb, S --> ε, as uvxyz. Show, step-by-step, how the corresponding word uv2xy2z can be derived from this CFG.

19. (Due date October 28) Use pumping lemma to prove that the language {anb2nc3n, n = 0, 1, ...} is not context-free.

20. (Due date November 4) Write a program that, given 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). You can assume that all the numbers are one-digit ones. Submit a printout of the code, and a printout of the example of what this program generates.

21. (Due date November 4) Use a general algorithm that we had in class to design a Turing machine that accepts exactly the words accepted by Automaton A from Problem 3. Illustrate, step-by-step, how it works, on the example of the word 00.

22. (Due date November 4) Use the main ideas behind the Turing machine that we had in class for recognizing the language {anbn} to design a Turing machine for recognizing the language {anbncn}. Illustrate, step-by-step, how it works, on two example: a word aabbcc that belongs to this language, and a word aaba that doesn't belong to the language.

23. (Due November 11) Design a Turing machine for computing n + 2 in unary code. Trace it on an example.

24. (Due November 11) Design a Turing machine for computing n + 2 in binary code. Assume that in the beginning, the binary number is placed on the tape starting with its lowest bit. Trace it on an example.

Hint: adding 210, i.e., in binary code, 102, can be done as follows:

• we ignore the lowest bit, and move one step to the right;
• then we follow the same procedure as when we add 1 in binary code:
• we change all 1s to 0s and keep going right, until we see either a 0 or a blank;
• once we encounter a 0 or a blank, we replace it with 1;
• after that, we move back to rewind the tape.

Example: to add 102 to the binary number 101102, which is stored on the tape as 01101, we ignore 0, and do the replacing. As a result, on the tape, we will have a sequence 00011, which represents the binary number 110002.

25. (Due November 11) Design a 3-tape Turing machine for adding two binary numbers:

• the first two tapes contain the two inputs a and b;
• the result a + b should be placed on the third tape.
Trace it on an example.

26. (Due November 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) = jn(n) + 1 is n is a valid numerical code of a (Java) program and jn halts on n;
• f(n) = 0 otherwise.
Write down the first 5 values f(0), ..., f(4) of the function f(n) for the following case:
• j0(n) = 1;
• 1 is not a valid numerical code of a program;
• j2(0) = j2(1) = 0; for inputs n larger than 1, the function j2(n) does not halt;
• j3(n) = n − 5;
• j4(n) = n * (n − 1).

27. (Due November 25) Write a method that emulates a Turing machine for computing. The input to this method should include:

• the number N of states q0, ..., qN − 1; we assume that q0 is a start state, and that the last state qN − 1 is a halt state;
• the number M of symbols s0, ... sM − 1; we assume that s0 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 qn and sees the symbol sm;
• an integer array symbol[n][m] that describes what symbol should be written on the tape if the Turing Machine in the state qn sees the symbol sm;
• a character array lr[n][m] that describes, for each state qn and for each symbol sm, 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.
This program needs to keep track of a current location of the head. Initially, this location is 0.

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
In this case:
• we have N = 4 states: q0 = start, q1 = inNumber, q2 = back, and q4 = halt;
• we have M = 2 symbols: s0 = _ and s1 = 1.
Here:
• 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] = _.

28. (Due December 2) The disadvantage of representing a tape as an array -- as in Problem 27 -- 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.
Modify your program for simulating the Turing machine by using this two-stacks representation of a tape.

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.