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
a
_{1}, - the final state a
_{2}, and - a sink
state a
_{3}.

- From a
_{1}, 0 leads us to a_{2}, any other symbol (1, +, or −) leads to the sink. - From
a
_{2}, any symbol leads to the sink.

- the starting state
a
- The
automaton corresponding to the language B also has three states:
- the starting state b
_{1}, - the final state
b
_{2}, and - a sink state b
_{3}.

- From b
_{1}, 0 or 1 leads us to b_{2}, any other symbol (+ or −) leads to the sink. - From b
_{2}, 0 or 1 lead us back to b_{2}, any other symbol (+ or −) leads to the sink.

- the starting state b

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 q
_{1}, and the two final states q_{2}and q_{3}. - The corresponding alphabet consists of two symbols: a and b.
- When you see a,
from q
_{1}you move to q_{2}, from q_{2}you move to q_{3}, and from q_{3}you move to q_{1}. - When you see b, from q
_{1}you move to q_{3}, from q_{2}you move to q_{1}, and from q_{3}you move to q_{2}.

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 {a^{n}b^{n}c^{n},
n = 0, 1, 2, ...} = {Λ, abc, aabbcc, aaabbbccc, ...}.

7. (Due February 16) In class, we had a pushdown automaton for
recognizing words of the type ww^{R}, where w is any word,
and w^{R} means the same word reversed.

For example, if w = ab, then w^{R} = ba, and
ww^{R} = abba.

The automaton that we came up with has 4 states:

- the starting state s,
- the reading state r,
- the checking state c, and
- the final state f.

- 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:
- ε, $ → ε.

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
ww^{R}. 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.

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.

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
a^{n}b^{n}:

- 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 reading state r,
- the checking state c, and
- the final state f.

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

- 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 q
_{0}, ..., q_{N − 1}; we assume that q_{0}is the start state, that the last-but-one state q_{N − 2}is the accept state, and the last state q_{N − 1}is the reject state; - the number M of symbols s
_{0}, ... s_{M − 1}; we assume that s_{0}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 q
_{n}and sees the symbol s_{m}; - an integer array symbol[n][m] that
describes what symbol should be on the tape after the Turing
Machine in the state q
_{n}sees the symbol s_{m}(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 q
_{n}and for each symbol s_{m}, 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.

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

- we have N =
6 states: q
_{0}= start, q_{1}= inNumber, q_{2}= state1, q_{3}= state0, q_{4}= accept, and q_{5}= reject; - we have M = 3 symbols:
s
_{0}= _, s_{1}= 0, and s_{2}= 1;

- 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) = j
_{n}(n) + 1 if n is a valid code of a Java program and j_{n}halts on n; - f(n) = 0 otherwise.

- j
_{0}(n) = 3 * n + 2; -
j
_{1}(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.