## Automata,

Homeworks for the course

CS
3350, Spring 2016

1. (February 29) Use a general algorithm for transforming a
context-free grammar into a pushdown automaton to design an
automaton corresponding to the context-free grammar with the
following rules:

S → 0A0

A → 1S1

S → ε

A → ε

Show, step-by step, how this automaton will recognize a sequence 0110
which can be generated by this grammar as follows: S → 0A0 →
01S10 → 0110.
2. (February 29) Use pumping lemma for finite automata to prove that
the language L consisting of all the words of the type waw^{R}b
is not regular, where a and b are letters, w is an arbitrary
word, and w^{R} is the same word in reserve order.

3. (March 2) Use pumping lemma for finite automata to prove that
the following language L is not regular: it is the language consisting
of all the words that have either more b's than a's or the same number
of a's and b's.