CS 3350 Automata, Computability, and Formal Languages
Fall 2017, Test 3

Name: __________________________________________________________

General comments:

Good luck!

1. Illustrate the pumping lemma for context-free grammars by showing how it will represent the word w = +01 which is generated by the CFG with starting variable S and rules S → N, S → IN, I → +, I → −, N → DN, N → D, D → 0, and D → 1 as uvxyz. Show, step-by-step, how the corresponding word uvvxyyz can be derived from this CFG.

2. Prove that the language of all the words that have an equal number of a's and b's, and twice as many c's is not context-free.

3. Design a Turing machine that, given a positive unary number n, adds 2 to this number. Test it, step-by-step, on the example of n = 1.

4. 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 3, 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.

5. Design a Turing machine that, given two unary numbers, computes their sum. Test it, step-by-step, on the example of 1 + 2.

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

7. Use the general algorithm to transform the following finite automaton for recognizing possibly signed binary integers to a Turing machine. This automaton has a starting state s, an intermediate state i, a final state f, and a sink state k, and the following transitions:
  • from s, + or − lead to i, while 0 or 1 lead to f;
  • from i, 0 or 1 lead to f, while + or − lead to sink;
  • from f, 0 or 1 lead to f, while + or − lead to sink.
Show, step-by-step, how your Turing machine will accept the word +01.

8. Use the general algorithm to transform the following PDA into a two-tape Turing machine. This PDA recognizes 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 pushdown automaton has 4 states:

  • the starting state s,
  • the reading state r,
  • 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:
    • ε, $ → ε.
Show, step-by-step, how the resulting Turing machine will recognize the sequence abba.

9. 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?

10. Formulate Church-Turing thesis. Is it a mathematical theorem? Is it a statement about the physical world?