Computer Science (Theory of Automata)

Question 2:   a. Give the context free grammars that generate the following languages. In both parts the alphabet S = {0, 1}

(i)                  {w | w contains at lest three 1’s}

(ii)                {w | the length of w is odd and its middle symbol is a 0}

b. Give context free grammars generating the following languages.

            (i) The set of strings over the alphabet {a, b} with more a’s than b’s

            (ii) {w#w | w^R is a substring of x for w, x ? {0, 1}^*}