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

1. (Due August 30) Design an automaton that recognizes identifiers in Java. Show, on two examples, how it works: an example of a correct identifier and an example of a string which is not a correct identifier. Reminder: a identifier in Java starts with a letter and may have letters, digits, or underscore symbols _ after that.

2. (Due August 30) Design an automaton that accepts only binary strings in which the number of 1s is equal to 1 modulo 3 (i.e., has 1, 4, 7, ... ones). For example, your automaton should accept a string 100 or a string 101110, but not a string 00111.

3. (Due August 30) 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 0s. This automaton has two states:
• a starting state b1 and
• a final state b2.

4. (Due September 6) 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, q2 and q3 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 September 6) 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 September 6) 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 September 6) Show, step-by-step, how to form a non-deterministic automaton corresponding to the following regular expression: 1(0* U 1).

8. (Due September 13) Show, step-by-step, how the general algorithm will produce a regular expression that corresponds to automaton that accepts the language of all the binary sequences that have even number of 1s. A finite automaton for recognizing this language is similar to Automaton B from Problem 3, the only difference is that in the new automaton, the state b1 is final and the state b2 is not final.

9. (Due September 20, extra credit if turned in by September 13) 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 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 numbers 0, 1, 2, ..., s − 1;
• when s = 2, symbols are 0 and 1, so we consider general binary sequences;
• when s = 3, symbols are 0, 1, and 2;
• etc.
• 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.

10. (Due September 20) 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 September 20) Let L be a language of all expressions consisting of open and close square brackets and of letters b and c, in which the number of open square brackets [ is equal to the number of closed square brackets ]. For example, the strings [b] and c]]b[[c are in this language, but the string [[b] is not. Prove that this language is not regular.

12. (Due September 20) Describe, step-by-step, how a pushdown automaton for recognizing the language {0n1n} -- which is described in the textbook and which we also described in class -- recognizes a sequence 00001111.

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

14. (Due October 4) Use the general algorithm to transform the following context-free grammar into a pushdown automaton: S --> 1T0, T --> 0S1, S --> ε, T --> ε. Show, step-by-step, how the word 1010, which is generated by the original context-free grammar as S --> 1T0 --> 10S10 --> 1010, will be accepted by the resulting pushdown automaton.

15. (Due October 11) The textbook has a 4-state pushdown automaton from that recognizes the language {wwR: w is in {0,1}*}; in my edition, it is Figure 2.19, it may have a different number in other editions. Use the general algorithm to transform this automaton into a context-free grammar. Show how the word 0110, which is accepted by this automaton, will be generated by this grammar.

16. (Due October 25 for extra credit, due November 1 for regular credit) Use the pumping lemma for pushdown automata to prove that the language {www: w is in {0,1}*} is not context-free. Hint: feel free to appropriately modify the book's proof about the language {www: w is in {0,1}*}.

17. (Due October 25) Step by step transform the following CFG to Chomsky normal form: S --> 1T0, T --> 0S1, S --> ε, T --> ε.

18. (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).
You can assume that all the numbers are one-digit ones. Comment: as with other programming assignments, submit a printout of the code, and a printout of the example of what this program generates.

19. (Due November 8) Show, on the first few steps of a Turing machine recognizing the language {anbncn, n = 0, 1, 2, ...}, how a Turing machine can be represented as a finite automaton with two stacks.

20. (Due November 8) Transform a finite automaton B from Problem 3 into a Turing machine. Show step-by-step, on an example of a word 101, how this word will be recognized by your Turing machine.

21. (Due November 22, for extra credit by November 15) Write a method that emulates a Turing machine. The input to this method should include:

• the number N of states q0, ..., qN − 1; we assume that q0 is the start state, that the last-but-one state qN − 2 is the accept state, and the last state qN − 1 is the reject 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 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
In this case:
• we have N = 7 states: q0 = start, q1 = inNumber, q2 = state1, q4 = state0, q5 = accept, and q6 = reject;
• we have M = 3 symbols: s0 = _, s1 = 0, and s2 = 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 --> state1, R means that state[1][2] = 2, symbol[1][2] = 2, and lr[1][2] = R, etc.

22. (Due November 15) Design a Turing machine for computing n − 2 in unary code; for n = 0 and for n = 1, it should return 0. Trace it on two examples: n = 1 and n = 4.

23. (Due November 29, for extra credit due November 22) The disadvantage of representing a tape as an array -- as in Problem 21 -- 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 the symbol at the head's location and all the symbols after that, while
• the first stack represents all the symbols before the head.
Modify your program for simulating the Turing machine by using this two-stacks representation of a tape.