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:

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 wawRb is not regular, where a and b are letters, w is an arbitrary word, and wR 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.