5. Design a pushdown automaton that would recognize the words of
the type a
, i.e., the language L = {bb,
abbb, aabbbb, ...}. Show, step by step, how your pushdown
automaton will recognize the word abbb.
as a sample.
6. Design a context-free grammar that would generate all the words
of the type a
^{n}b
^{n+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 a
^{n}b
^{n} 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: {a
^{2n}b
^{n}c
^{2n}} =
{Λ, 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.