## CS 3350 Automata, Computability, and Formal Languages Spring 2017, Test 2

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 of time, just follow the few first steps of the corresponding algorithm;
• each question will be graded on its own merit; so, for example, if on one stage, you got a wrong context-free grammar, but on the second stage, you correctly apply the Chomsky normal form algorithm to the resulting grammar, you will get full credit for the second stage.
Good luck!

1-4. Finite automata. Let us consider the following finite automaton (FA) for recognizing words in the alphabet {a,b} that only have a's (and do not have any b's). This automaton has two states: the start state which is also final, and the sink state. From the start state, letter 'a' leads back to the same state, while letter 'b' leads to the sink state.

1. On the example of the word aaa accepted by the given automaton, show how this word will be represented as xyz according to the pumping lemma for FA. For this sequence, check -- by tracing step-by-step -- that the sequence xy2z is indeed accepted by this automaton.

2. Use the general algorithm to transform the given FA into a context-free grammar (CFG). Show, step-by-step, how the word aaa can be derived in this CFG.

3. Use the general algorithm to transform the given FA into a Turing machine (TM). Show, step-by-step, how this TM will accept the word aaa.

4. Use the Pumping Lemma for FA to prove that the language {pnqn} = {Λ, pq, ppqq, pppqqq, ...} cannot be recognized by a finite automaton.

5-8. Pushdown automata (PDA) and context-free grammars (CFG). The following CFG generates the language {pnqn}: it has the starting variable S and the rules S → ε, S → pSq.

5. Show, step-by-step, how the word ppqq will be generated by this CFG.

6. Use the general algorithm to generate a PDA that recognizes the words generated by this CFG -- and only these words. Show, step-by-step, how the resulting PDA will accept the word ppqq.

7. Use the general algorithm to transform the given CFG into Chomsky normal form.

8. On the example of the word ppqq generated by the given CFG, show how this word will be represented as uvxyz according to the pumping lemma for CFG. For this sequence, check -- by tracing step-by-step -- that the sequence uv2xy2z is indeed generated by this CFG.

9. Use the general stack-based algorithms to show:
• how the compiler will transform the expression (2 − 4) * (1 + 3) into postfix form, and
• how it will compute the value of the resulting postfix expression.

10. Design a Turing machine (TM) for subtracting 1 from the input n in binary code; assume that the input is non-zero. Trace, step-by-step, how your TM will perform when n = 102 (i.e., when n is equal to number 2 as described in the binary code).