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

1. (Due January 19) Design an automaton that recognizes real numbers in Java (both fixed-point and floating-point ones), and check it on two examples:

• a legitimate Java real number, and
• a sequence of symbols which is not a legitimate real number.

2. (Due January 26) Use the algorithm that we learned on January 19, with pairs of states from two automata as states of the new deterministic automaton, to describe 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, 0 leads us to a2, any other symbol (1, +, 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 b2, any other symbol (+ or −) leads to the sink.
• From b2, 0 or 1 lead us back to b2, any other symbol (+ or −) leads to the sink.

3. (Due January 26) Use the algorithms that we learned in class on January 24 to design a non-deterministic automaton recognizing the language (0 U 1)(0 U 1)*:

• start with non-deterministic automata recognizing 0 and 1; for example, a non-deterministic automaton recognizing 0 has two states, the start state and the final state, and the only transition is that when we are in the start state, 0 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 0 U 1;
• apply the general algorithm for the Kleene star to your automaton recognizing 0 U 1, and come up with an automaton that recognizes the language (0 U 1)*;
• apply the general algorithm for the concatenation to your automata recognizing 0 U 1 and (0 U 1)*, and get an automaton recognizing the language (0 U 1)(0 U 1)*.

4. (Due February 2) Use the general algorithm that we learned in class to come up with a regular expression that describes all the words accepted by the following automaton:

• This automaton has 3 states, the starting state q1, and the two final states q2 and q3.
• The corresponding alphabet consists of two symbols: a and b.
• When you see a, from q1 you move to q2, from q2 you move to q3, and from q3 you move to q1.
• When you see b, from q1 you move to q3, from q2 you move to q1, and from q3 you move to q2.

5. (Due February 9) Let us consider the following automaton: the automaton from the Problem 4 accepts the following word: aabbaa.

• 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 word xyyz is also accepted by this automation.

6. (For extra credit, due February 9) Prove that the following language is not regular {anbncn, n = 0, 1, 2, ...} = {Λ, abc, aabbcc, aaabbbccc, ...}.

7. (Due February 16) 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:
• ε, \$ → ε.
Add the letter d, o, and r to this automaton, and show, step-by-step, how this automaton will recognize the sequence doorrood.

8. (Due February 16, for extra credit) Modify the pushdown automaton described in Problem 7 so that the new automaton will recognize all palindroms, not only palindroms of the type wwR. For example, the word madam should be recognized by this palindrom. Show, on an example of a palindrom different from what we had in class, how your automaton will recognize this palindrim.

9. (Due February 16) In class, we considered a context-free grammar (CFG) that generates palindroms. This CFG has the following rules:

• S → ε,
• S → a,
• S → b,
• ...,
• S → z,
• S → aSa,
• S → bSb,
• ...,
• S → zSz.
On an example of a palindrom different from what we considered in class, show, step-by-step, how this palindrom will be generated by this grammar.

10. (Due February 23) 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 1011 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.

11. (Due February 23) Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to the context-free grammar with the following rules:

• S → ε,
• S → d,
• S → o,
• S → r,
• S → dSd,
• S → oSo,
• S → rSr.
On the example of the word doorrood, show step-by-step how this word will be recognized by the resulting pushdown automaton.

12. (Due March 7) Apply, step-by-step, the general algorithm for transforming a context-free grammar into Chomsky normal form to the following context-free grammar. This grammar generates both palindromes composed of letters a and b and words of the type anbn:

• S → P,
• P → ε,
• P → aPa,
• P → bPb,
• S → W,
• W → ε,
• W → aWb.

13. (Due March 2 for extra credit, due March 7 for regular credit) Apply, step-by-step, the general algorithm of converting a pushdown automaton to a context-free grammar to the following pushdown automaton. This pushdown automaton has four 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
• From r to c, we have a jump:
• ε, ε → ε
• From c to c, the transitions are:
• a, a → ε
• b, b → ε
• From c to f, the only transition is:
• ε, \$ → ε

14. (Due March 9) 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.

15. (Due March 9) Illustrate the pumping lemma for context-free grammars by showing how it will represent the word s = aaacbbb which is generated by the CFG with rules S → ε, S → a, S → b, S → c, S → aSb, S → bSa, and S → cSc, as uvxyz. Show, step-by-step, how the corresponding word uvvxyyz can be derived from this CFG.

16. (Due March 23) 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 March 23) Design a Turing machine that, given a unary number n, adds 2 to this number. Test it, step-by-step, on some example.

18. (Due March 23) Design a Turing machine that, given a binary number n, adds 2 to this number. Test it, step-by-step, on some example.

19. (Due March 30) 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.

20. (Due March 30) 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.

21. (Due April 13) In the proof that the halting problem is not algorithmically solvable, we use a diagonal function
f(n) which was defined as follows:

• f(n) = jn(n) + 1 if n is a valid code of a Java program and jn halts on n;
• f(n) = 0 otherwise.
Write down the first 3 values f(0), f(1), and f(2) of the diagonal function f(n) for the following case:
• j0(n) = 3 * n + 2;
• j1(n) = n * n; and
• 2 is not a valid numerical code of a program

22. (Due April 20) Not all algorithms are feasible, but, unfortunately, we do not have a perfect definition is feasibility. Give two examples:

• an example of an algorithm which is feasible according to the current definition but not practically feasible, and
• an example of an algorithm which is practically feasible but not feasible according to the current definition.
These examples must be different from what we had in class.