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

Name: __________________________________________________________

• you are allowed up to 5 pages of handwritten notes;
• if you need extra pages, place your name on each extra page;
• the main goal of most questions is to show that you know the corresponding algorithms; so, if you are running out of time, just follow the few first steps of the corresponding algorithm.
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.