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

General comment: Unless explicitly specified, each homework should be turned in on a sheet of paper:

• if requested, draw an automaton like we did in class and like the book does,
• do whatever else is requested,
• add the last 4 digits of your ID number on top, and
• place your homework on the instructor's desk in the classroom by the beginning of the class on the day when the homework is due.

1. (Due August 29) In class, we studied an automaton for recognizing signed or unsigned binary integers. This automaton has 4 states: start (st), sign (si), integer (i), and error (e). Start is the starting state, integer is the only final state. The transitions are as follows:

• from st, 0 or 1 lead to i; + or − lead to si, every other symbol leads to e;
• from si, 0 or 1 lead to i, every other symbol leads to e;
• from i, 0 or 1 lead to i, every other symbol leads to e;
• from e, every symbol leads to e.
Trace, step-by-step, how this finite automaton will check whether the following two words (sequences of symbols) represent syntactically correct binary integers:
• the word −0 (which this automaton should accept) and
• the word −0−0 (which this automaton should reject).

2. (Due August 29) In class, we had yet another finite automaton for recognizing signed or unsigned binary integers. This new automaton has 5 states: the starting state start (st), the state sign_read (sr), the state signed_integer (si), the state unsigned_integer (u), and the sink (error) state e. This automaton has two final states: si and u. The transitions are as follows:

• from st, + or − lead to sr, 0 or 1 lead to u, every other symbol leads to e;
• from sr, 0 or 1 lead to si, any other symbol leads to e;
• from si, 0 or 1 lead to si, any other symbol leads to e;
• from u, 0 or 1 lead to u, any other symbol leads to e;
• from e, any symbol leads to e.
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;
• δ: 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 staring state, and
• F is the set of all final states.

3. (Due August 29) Similarly to the automaton from Problem 1 (that we analyzed in class), draw an automaton for recognizing all possible signed and unsigned integers (not necessary binary), so that this automaton will also recognize numbers like 32, +32, and −32.

4. (Due September 5) Let A be an automaton described in Problem 1. Let B be the following automaton that accepts all the strings that contain only +s, 0s, and 1s but not any other symbols. This automaton has two states: the start state which is also a final state, and the sink state. The transitions are as follows:

• from the start state, +, 0, or 1 lead back to the start state, every other symbol leads to sink;
• from the sink state, any symbol leads back to sink.
Use the algorithm that we had in class to describe the following two new automata:
• the automaton that recognizes the union A U B of the two corresponding languages, and
• the automaton that recognizes the intersection of the languages A and B.
Test these automata step-by-step on the following words:
• test the union automaton on the example of the words +0+0 (that it should accept) and −0−0 (that it should reject);
• test the intersection automaton on the example of the words +0 (that it should accept) and −0 (that it should reject).

5. (Due September 12) Use the general algorithm that we learned in class to design a non-deterministic finite automaton that recognizes the language (0 U 1)(1 U 2).

6. (Due September 19) Use the general algorithm that we learned in class to design a non-deterministic finite automaton that recognizes the language (0 U 1)(1 U 2)*: a composition of the union 0 U 1 and a Kleene star (1 U 2)*. Use a general algorithm to transform this non-deterministic automaton into a deterministic one.

7. (Due September 26) Apply the general algorithm for transforming the finite automaton into a regular language (i.e., a language described by a regular expression) to Automaton B from Problem 4. Assume that we are allowing four possible symbols: in addition to +, 0, and 1, we also have a symbol X.

8. (Due September 26) Automaton from Problem 1 accepts the word +10.

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

9. (Due October 3) Write a method that emulates a general finite automaton. The input to this method should include:

• the number N of states q0, ..., qN − 1; we assume that q0 is the start state;
• the number M of symbols 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. 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.

10. (Due October 3) Prove that the following language is not regular {0n1n2n} = {Λ, 012, 001122, 000111222, ...}.

11. (Due October 10) In class, we had a pushdown automaton for recognizing words of the type wwR, where w is any word, and wR means the same word reversed. For example, if w = cat, then wR = tac, and wwR = cattac.

The automaton that we came up with has 4 states:

• the starting state s,
• the checking state c, and
• the final state f.
The transitions are as follows:
• 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:
• ε, \$ → ε.
Show, step-by-step, how this automaton will recognize the sequence cattac.

12. (Due October 10) 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.
On an example of a palindrome cattac, show, step-by-step, how this palindrome will be generated by this grammar.

13. (Due October 10) On the example of the Automaton B from Problem 4, 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 +1+ 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.

14. (Due October 17) Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to the context-free grammar from Problem 12 (limit yourselves to only three letters a, c, and t). Show, step by step, how the derivation of the word cattac in the original grammar translates into the acceptance of this word by the resulting pushdown automaton.

15. (Due October 17) Prove that the following language is not context-free: {0n12n23n} = {Λ, 011222, 001111222222, 000111111222222222, ...}.

16. (Due October 17) On the example of the word cattac generated by a grammar from Problem 12, show how this word will be represented as uvxyz according to the Pumping Lemma. Show how the words uxz and uvvxyyz will be generated by this grammar.

17. (Due October 24) Apply the general algorithm to transform the grammar from Problem 12 into the Chomsky normal form; for simplicity, only consider letters a and b; full credit if you do preliminary step and Step 0. Extra credit if you perform all the steps of the algorithm.

18. (Due October 31) Finish applying the general algorithm to transform the grammar from Problem 12 into the Chomsky normal form -- if you have not yet done that for extra credit. For simplicity, only consider letters a and b.

19. (Due October 31) Apply, step-by-step, the general algorithm of converting a pushdown automaton to a context-free grammar to the pushdown automaton from Problem 11. Explain how the acceptance of the word cattac by this automaton will be translated into a derivation of this word in the resulting grammar.

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

21. (Due November 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 are one-digit ones. Comments:
• 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.

22. (Due November 14) Design a Turing machine that, given a positive unary number n, subtracts 1 from this number. Test it, step-by-step, on the example of n = 5.

23. (Due November 14) Design a Turing machine that, given a positive binary number n, subtracts 1 from this number. Test it, step-by-step, on the example of n = 5.

24. (Due November 14) Transform a finite automaton B from Problem 4 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.

25. (Due November 21) 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 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 on the tape after the Turing Machine 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 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. Feel free to use Java, C, C+++, Fortran, or any programming language in which the code is understandable.

26. (Due November 28) As we discuss 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.
On the example a Turing machine from Problem 24, 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.

27. (Due December 5) 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.
These examples should be different from what you learned in class -- a minor difference is OK.

28. (Due December 5) 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?