## CS 3350 Automata, Computability, and Formal Languages Spring 2020, 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 when answering to the first part of the question, you got a wrong automaton, but on the second part, you correctly traced the new automaton, you will get full credit for the second part.
Good luck!

1. Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to the following context-free grammar with the starting variable S: S → dcB; B → cdS; S → ε. Show, step by step, how the word dccd will be accepted by this automaton. Its derivation in the given grammar is straightforward: S → dcB → dccdS → dccd.

2. Design a finite automaton for recognizing binary sequences that have even number of a's or even number of bs. Assume that the input strings contain only symbols a and b. The easiest is to have 4 states:
• a final state ee in which we have even number of a's and even number of b's,
• a final state eo, in which we have even number of a's and odd number of b's, and
• similarly defined states oe (odd-even, final) and oo (odd-odd, not final).
You just need to describe transitions between these states, and which states are final. Show, step-by-step, how your automaton will accept the string aba. Show how the general algorithm will produce a context-free grammar that generates all the words accepted by this automaton -- and only words generated by this automaton. On the example of a word aba accepted by this automaton, show how the tracing of acceptance of this word by the finite automaton can be translated into a generation of this same word by your context-free grammar.

3. Use the general algorithm to transform the grammar from Problem 1 into Chomsky normal form.

4. Use the general algorithm to transform the following pushdown automaton into a context-free grammar. This automaton has 4 states:
• the starting state s,
• 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:
• 0, ε → 1;
• 1, ε → 0;
• From r to c, we have a jump ε, ε → ε.
• From c to c, the transitions are:
• 0, 0 → ε
• 1, 1 → ε
• From c to f, the only transition is:
• ε, \$ → ε.
Show, step-by-step, how the resulting grammar will generate the sequence 0101.

5. Show, step by step, how the stack-based algorithm will transform the expression 5 − (3 − 7) into a postfix expression, and then how a second stack-based algorithm will compute the value of this postfix expression.

6. For the grammar from Problem 1, show how the word dccd can be represented as uvxyz in accordance with the pumping lemma for context-free grammars. Show that the corresponding word uvvxyyz will be generated by this grammar.