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

General comment: Unless explicitly specified, each homework should be turned in on a sheet of paper: draw an automaton like we did in class and like the book does, do whatever else needed, add your name on top and turn it in by the beginning of the class on the day when the homework is due.

1. (Due September 6) A recommended name for a class in Java should start with a capital letter, and have only letters (small or capital), digits, and an underscore symbol _. Design an automaton that recognizes such names, and check it on two examples:

• a recommended Java class name, and
• a sequence of symbols which is not a recommended Java class name.

2. (Due September 6) Use the algorithm that we learned in class, with pairs of states from two automata as states of the new deterministic automaton, to design the automata recognizing the union and the intersection of the languages A and B corresponding to the following automata:

• The automaton corresponding to the language A has three states:
• the starting state a1,
• the final state a2, and
• a sink state a3.
The transitions are as follows:
• From a1, 1 leads us to a2, any other symbol (0, +, or −) leads to the sink.
• From a2, any symbol leads to the sink.
• The automaton corresponding to the language B also has three states:
• the starting state b1,
• the final state b2, and
• a sink state b3.
The transitions are as follows:
• From b1, 0 or 1 leads us to b3, any other symbol (+ or −) leads to the b2.
• From b2, 0 or 1 lead us back to b2, any other symbol (+ or −) leads to the sink.

3. (Due September 13) Use the algorithm that we learned in class to design a non-deterministic automaton recognizing the language (a U b)*(a U b):

• start with non-deterministic automata recognizing a and b; for example, a non-deterministic automaton recognizing a has two states, the start state and the final state, and the only transition is that when we are in the start state, a leads to the final state;
• use the general algorithm for the union of languages represented by non-deterministic automata to design a non-deterministic automaton recognizing the language a U b;
• apply the general algorithm for the Kleene star to your automaton recognizing a U b, and come up with an automaton that recognizes the language (a U b)*;
• apply the general algorithm for the concatenation to your automata recognizing (a U b)* and a U b, and get an automaton recognizing the language (a U b)*(a U b).

4. (Due September 20) Use the general algorithm to transform the non-deterministic automaton from Problem 3 into a deterministic one.

5. (Due September 20) 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.

6. (Due September 27) Apply the general algorithm for transforming the finite automaton into a regular language to Automaton B from Problem 2.

7. (Due September 27) Automaton B from Problem 2 accepts the word +010.

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

8. (Due October 4, due September 27 for extra credit) Prove that the following language is not regular {0n1n2n} = {Λ, 012, 001122, 000111222, ...}.

9. (Due October 18) 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 = ab, then wR = ba, and wwR = abba.

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

10. (Due October 18) 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 abba, show, step-by-step, how this palindrome will be generated by this grammar.

11. (Due October 18) On the example of the Automaton B from Problem 2, 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 +010 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.

12. (Due October 25, extra credit if turned in on October 18) Apply, step-by-step, the general algorithm for transforming a context-free grammar into Chomsky normal form to the context-free grammar from Problem 10 (limit yourselves to only two letters a and b).

13. (Due October 25) Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to the context-free grammar from Problem 10.

14. (Due November 1) Apply, step-by-step, the general algorithm of converting a pushdown automaton to a context-free grammar to the pushdown automaton from Problem 9. Explain how the acceptance of the word abba by this automaton will be translated into a derivation of this word in the resulting grammar.

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

16. (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. 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.

17. (Due November 8) Illustrate the pumping lemma for context-free grammars by showing how it will represent the word s = acb which is generated by the CFG with starting variable S and rules A → ε, S → AS, S → SB, A → a, B → b, and S → c, as uvxyz. Show, step-by-step, how the corresponding word uvvxyyz can be derived from this CFG.

18. (Due November 15) Prove that the language of all the words that have equal number of a's, b's, and c's is not context-free.

19. (Due November 15) Design a Turing machine that, given a positive unary number n, subtracts 1 from this number. Test it, step-by-step, on some example.

20. (Due November 15) Design a Turing machine that, given a positive binary number n, subtracts 1 from this number. Test it, step-by-step, on some example.

21. (Due November 15) Transform a finite automaton B from Problem 2 into a Turing machine. Show step-by-step, on an example of a word 010, how this word will be recognized by your Turing machine.

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

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 = 6 states: q0 = start, q1 = inNumber, q2 = state1, q3 = state0, q4 = accept, and q5 = 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.

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

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

25. (Due November 22, by November 15 for extra credit) As we discussed 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 21, 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.

26. (Due November 22) Apply the general algorithm for transforming a PDA into a 2-tape Turing machine to the PDA that recognizes words of the type anbn. Show, step-by-step, how your Turing machine will accept the word aabb.