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

Name: __________________________________________________________

General comments:

Good luck!

1-2. Transform, step by step, the grammar with rules S → ε, S → aSb, and S → bSa to Chomsky normal form. Show how the word baba will be generated in the resulting Chomsky-normal-form grammar.

3-4. Use a general algorithm for transforming PDA into CFG to design a CFG that corresponds to the following pushdown automaton. This automaton has two states: the starting 0-state s0 and the 1-state s1. Both states are final. The transitions are:
  • From s0 to s0, the transition is 0, ε → y, for some symbol y
  • From s0 to s1, the transition is 1, y → ε.
  • From s1 to s1, the transition is 1, y → ε.
Show, step by step, how the word 01 will be generated by the resulting grammar.

5. Use the general stack-based algorithms to show:
  • how the compiler will transform the expression (1 − 10) / (8 − 11) into postfix form, and
  • how it will compute the value of the resulting postfix expression.

6. Illustrate the pumping lemma for context-free grammars by showing how it will represent the word w = +1.00 which is generated by the CFG with starting variable V and rules V → SN.N, V → N.N, S → +, S → −, 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.

7. Prove that the language of all the words of the type anbncndn, n = 0, 1, 2, ..., is not context-free.

8. 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 = 0.

9. (For extra credit) Design a Turing machine that, given two unary numbers, computes their sum. The input is represented as two numbers separated by blank space. Test it, step-by-step, on the example of 2 + 2.

10. (For extra credit) Let us consider possibly signed binary integers. Such numbers can be described by the following finite automaton. 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 − leads to sink;
  • from f, 0 or 1 lead to f, while + or − lead to sink.
Use the general algorithm to transform this finite automaton into a Turing machine. Show, step-by-step, how your Turing machine will accept the word +01.