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

General comment. The main purpose of most homeworks is to show how well you understand the algorithms.

In many cases, the resulting finite automata, pushdown automata, and Turing machines can be simplified, but please first literally apply the algorithm so that we know that you can use it.

If in addition to this, you also show how to make the corresponding Turing machine or finite automaton or whatever more concise, nothing wrong with that, the TA may even give you some extra points (if she has time to grade these additional things). But the most important thing is to show that you can follow the algorithm.

For simple examples that we give you as homeworks:

• you may immediately see how to convert, e.g., a context-free grammar into a Chomsky normal form,
• but if someone gives you a more complex case, you will have to use the algorithm.
So, it is important to learn how to follow the algorithm.

If you deviate from the algorithm, how do we know that you learned the algorithms? It was the same with sorting.

• Of course, if someone gives you a list of 4 numbers on the test, you can sort them yourself easily.
• The purpose of the question was that you show that you understand mergesort, quicksort etc., not that you sort 4 numbers.
In general:
• If after you show that you understand the algorithm you also provide a simpler answer -- great,
• but not instead of following the algorithm.

1. (Due September 2) In class, we designed automata for recognizing integers and real numbers.

1.1. Use the same ideas to describe an automaton for recognizing names of classes in Java. In Java, this name should start with a capital letter, and contain only letters, digits, or the underscore symbol. To describe an automaton, draw a picture like we did in class.

A natural idea is to have 3 states: start (s), correct class name (c), and error (e). Start is the starting state, c is the only final state. The transitions are as follows:

• from s, any capital letter A, ..., Z lead to c, every other symbol leads to e;
• from c, any digit, any letter, and the underline symbol lead back to c, every other symbol leads to e;
• from e, every symbol leads back to e.

1.2. Trace, step-by-step, how this finite automaton will check whether the following two words (sequences of symbols) are correct names for Java classes:

• the word Java (which this automaton should accept) and
• the word C++ (which this automaton should reject).

1.3. Write down the tuple <Q, Σ, δ, q0, F> corresponding to this automaton:

• Q is the set of all the states,
• Σ is the alphabet, i.e., the set of all the symbols that this automaton can encounter; for simplicity, consider only four symbols: the plus sign, letters a and A, and an underscore;
• δ: Q x Σ → Q is the function that describes, for each state q and for each symbol s, the state δ(q,s) to which the automaton that was originally in the state q moves when it sees the symbol s (you do not need to describe all possible transitions this way, just describe two of them);
• q0 is the starting state, and
• F is the set of all final states.

1.4. Apply the general algorithm for union and intersection to:

• this automaton as Automaton A, and
• a more realistic version of an automaton for recognizing unsigned integers -- that automaton is described in the examples lecture -- as Automaton B; in the example described in the lecture, we assumed, for simplicity, that, in addition to 0 and 1, only the symbol a is allowed; in reality, any other symbol different from 0 and 1 -- including symbols A and underscore -- leads to the error state e.
For simplicity, in your automaton for recognizing the union and intersection of the two languages, feel free to assume that you only have symbols 0, a, A, underscore, and +.

2. (Due September 2)

• Use the general algorithm that we learned in class to design a non-deterministic finite automaton that recognizes the language (+ U −)(0 U 1)*; reminder:
• 0 is a language consisting of only one 1-symbol word 0;
• AB means concatenation;
• transform the resulting non-deterministic finite automaton into a deterministic one.

3. (Due September 9) Apply the general algorithm for transforming the finite automaton into a regular language (i.e., a language described by a regular expression) to the following automaton. This automaton has two states: s (= straight-A student) and e (= everyone else); s is the starting state, it is also the final state. The only two symbols are A and B. From s, A leads back to s, and B leads to e. From e, any symbol leads back to e.

4. (Due September 9) Prove that the following language is not regular {a2nbn, n = 0, 1, 2, ...} = {Λ, aab, aaaabb, aaaaaabbb, ...}.

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

• the number N of states; these states are q0, ..., qN − 1; we assume that q0 is the start state;
• the number M of symbols; these states are s0, ... sM − 1;
• an integer array state[n][m] that describes to what state the finite automaton moves if it was in the state qn and sees the symbol sm;
• a boolean array final[n] that tells us, for each state, whether this state is final or not.
This program needs to keep track of a current state. Initially, this location is 0.

Your program should emulate the work of the finite automaton step-by-step. Turn in:

• a file containing the code of the method,
• a file containing the code of the program that you used to test this method, and
• a file containing 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 16) Show, step by step, how the following pushdown automaton will recognize a sequence ++−−. This pushdown automaton has two states:

• the starting state A, and
• the final state B.
The transitions are as follows:
• From A to A, the transition is +, ε, → +;
• From A to B, the transition is: −, + → ε;
• From B to B, the transition is −, + → ε.

7. (Due September 16) Show, step by step, how the grammar with rules S → ε and S → +S− will generate the word ++−−.

8. (Due September 16) In a lecture, we described an algorithm that, given a finite automaton, produces a context-free grammar -- a grammar that generate a word if and only if this word is accepted by the given automaton.

• On the example of the automaton from Homework 3, show how this algorithm will generate the corresponding context-free grammar.
• On the example of a word AAA 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.

9. (Due September 16) Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to context-free grammar described in Problem 7. Show, step by step, how the word ++−− will be accepted by this automaton.

10. (Due October 7) Transform the grammar from Homework 7 into Chomsky normal form.

11. (Due October 7) Use the general algorithm to transform the pushdown automaton from Problem 6 into a context-free grammar. Show, step-by-step, how the resulting grammar will generate the word ++−−.

12. (Due October 7) Show, step by step, how the stack-based algorithm will transform the expression (1 − 3) * (5 − 7) into a postfix expression, and then how a second stack-based algorithm will compute the value of this postfix expression.

13. (Due October 14) 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 in the arithmetic expression are one-digit numbers, i.e., each of these numbers is either 0, or 1, or 2, ..., or 9. For example, your program should correctly process expressions like 2+3*4, but there is no need to process expressions like 11+22. For simplicity, assume that the only arithmetic operations are addition +, subtraction −, and multiplication *.

• as with all programming assignments for this class, submit a file containing the code, and a file containing 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.

14. (Due October 21) For the LL(1) grammar that we studied in class, with rules S → F, S → (S + F), and F → a, show how the word ((a + a) + a) can be represented as uvxyz in accordance with the pumping lemma for context-free grammars. Show that the corresponding word uvvxyyz will be generated by this grammar.

15. (Due October 21) Prove that the language consisting of all the words that have equal number of +'s and −'s and exactly two times as many opening parentheses is not context-free.

16. (Due November 4) Design a Turing machine that, given a positive unary number n, add 2 to this number. Test it, step-by-step, on the example of n = 2.

17. (Due November 4) Design a Turing machine that, given a positive binary number n greater than or equal to 8, subtracts 8 from this number. Test it, step-by-step, on the example of n = 9.

18. (Due November 4) Use the general algorithm to transform a finite automaton from Homework 3 into a Turing machine. Show step-by-step, on an example of a word AAA, how this word will be recognized by your Turing machine.

19. (Due November 4) As we discussed in a lecture, 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.
On the example a Turing machine that computes n − 1 for a binary number n = 4, show, step-by-step:
• 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.

20. (Due November 11) Write a method that emulates a general 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 head of the Turing machine changes if it was in the state qn and sees the symbol sm;
• an integer array symbol[n][m] that describes what symbol should be on the tape after the head in the state qn sees the symbol sm (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 qn and for each symbol sm, whether the head 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. Feel free to use Java, C, C+++, Fortran, or any programming language in which the code is understandable.

21. (Due November 11) Give two examples:

• an example of computation time which makes an algorithm feasible according to the formal definition but not practically feasible, and
• an example of computation time for which the corresponding algorithm is practically feasible, but not feasible according to the formal definition.
These examples should be different from what you learned in class -- a minor difference is OK.

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

23. (Due November 18) Prove that the cubic root of 5 is not a rational number.