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

Last 4 digits of your UTEP ID number: ____________________________

• you are allowed up to 5 pages of handwritten notes;
• if you need extra pages, place the last 4 digits of ID number 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-2. Use a general algorithm to transform the following finite automaton into the corresponding regular expression.

• This automaton has two states: a state s1 which is a start state and a final state, and another state s2.
• In the state s1, a and b lead to s2, and c leads to s1.
• In the state s2, a and c lead to s1, and b leads to s2.

3. Automaton from Problem 1-2 accepts the word abc.
• Trace, step-by-step, that this word is indeed accepted by the given automaton.
• Use this tracing to find the parts x, y, and z of this word corresponding to the Pumping Lemma.
• Trace that the words xyyz and xyyyz are also accepted by this automaton.

4. Prove that the language {anb2n} = {Λ, abb, aabbbb, aaabbbbbb, ...} is not regular.

5. Design a pushdown automaton that would recognize the words of the type anbn+2, i.e., the language L = {bb, abbb, aabbbb, ...}. Show, step by step, how your pushdown automaton will recognize the word abbb. Hint: use a pushdown automaton for recognizing the words of the type anbn as a sample.

6. Design a context-free grammar that would generate all the words of the type anbn+2, i.e., the language L = {bb, abbb, aabbbb, ...}. Show, step by step, how your grammar will generate the word abbb. Hint: use a context-free grammar for generating the words of the type anbn as a sample. There, we had rules S → ε and S → aSb, now a slight modification is needed.

7. Use a general algorithm that we had in class -- for transforming a finite automaton into a context-free grammar -- to generate a context-free grammar that corresponds to the following finite automaton for recognizing unsigned integers. For simplicity, assume that we only allow letters a and b and digits 0 and 1. This automaton has three states: the starting state s, the final state f, and the sink state k.
• From s, any letter (a or b) lead to k, while any digit leads to f.
• From f, any digit leads to f, and letter leads to k.
Show, step by step, how your grammar generates a word 010.

8. Use a general algorithm for transforming CFG into PDA to design a pushdown automaton which is equivalent to the the grammar with rules S → ε, S → 0S1, and S → 1S0. Show, step by step, how the word 1010 will be accepted by the resulting pushdown automaton.

9. (For extra credit) Prove that the following language is not context-free: {a2nbnc2n} = {Λ, aabcc, aaaabbcccc, aaaaaabbbcccccc, ...}.

10. (For extra credit) On the example of the word 1010 generated by a grammar from Problem 8, show how this word will be represented as uvxyz according to the Pumping Lemma. Show how the words uxz and uvvxyyz will be generated by this grammar.