CS 3350 Automata, Computability, and Formal Languages
Fall 2016, Test 2

Name: __________________________________________________________

1. Use the algorithm that we had in class to transform the following context-free grammar into Chomsky normal form. This grammar describes simple arithmetic expressions (E), combining numbers (N) 0 and 1 with + and -. The starting variable is E, the rules are: E --> N, E --> N+E, N --> 0, N --> 1, E --> N−E.

2. Use the general algorithm to design a (non-deterministic) pushdown automaton that recognizes exactly the context-free language described in Problem 1. Show, step-by-step, how a word 1+0 will be accepted by this automaton.

3. Apply, to pushdown automaton that you designed in Problem 2, the general algorithm of transforming a pushdown automaton into a context-free grammar, and show how this new grammar will generate the word 1+1. (If you are running out of time, just a few steps of this algorithm will be OK.)

4. In the context-free grammar described in Problem 1, we can derive the sequence 0+1+1 as follows:
  • first, we use the rule E --> N+E;
  • then, we use the rules N --> 0 and E --> N+E;
  • after that, we use the rules N --> 1 and E --> N;
  • finally, we use the rule N --> 1.
Draw a tree that describes this derivation. Use this tree to determine the subdivision of this sequence into u, v, x, y, and z. Then, for i = 2, draw a tree explaining how the corresponding sequence uvixyiz can be derived in this grammar.

5. Use pumping lemma for pushdown automata to prove that the language consisting of all the words of the type 1n0n1n0n cannot be recognized by a pushdown automaton. Can you use the same lemma to prove that the language 1n0n cannot be generated by a context-free grammar?

6. Use the general algorithm to design a Turing machine that is equivalent to the following finite automaton. This automaton helps to check whether a person is a saint. The alphabet consists of two symbols: + ("good deed") and − ("bad deed"). A person is a saint if he or she performed at least one good deed and none bad deeds. The automaton has three states: b ("born", starting state), p ("perfect so far", final state), and i ("imperfect").
  • From each state, − leads to the state i.
  • The state i is a sink (once in i, we stay in i).
  • From p, + stays in p.
  • From b, + leads to p.
Show, step-by-step, how this Turing machine will reject a sequence consisting of a minus; and a plus as not corresponding to a saint.

7. Use the general stack-based algorithms to show:
  • how the compiler will transform the expression 2 + (3 − 4 * 5) into inverse Polish notation, and
  • how it will compute the value of this expression.

8-9. Design a Turing machine that computes the function n + 2 = n + 102 in binary. Trace it on the example of n = 1. Show, step-by-step, how the tape of the Turing machine can be represented as two stacks.

10. Computability:
  • Formulate Church-Turing thesis.
  • Is it a mathematical theorem? A statement about the physical world?
  • Formulate the halting problem. Is it computable?