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

Last 4 digits of your UTEP ID number: ____________________________

General comments:

Good luck!

1-2. Use a general algorithm to transform the following finite automaton into the corresponding regular expression.

3. Automaton from Problem 1-2 accepts the word abc.

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.