1. Suppose A = {0,1}. Describe all strings belonging to A∗.
2. Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 0100.
3.Let G be the phrase-structure grammar with vocabulary V = {A,B,a,b,S}, terminal element set T = {a,b}, start symbol S, and production set P = {S → ABa,S → Ba,A → aB,AB → b,B → ab}. Which of these are derivable from A?
A) babaa B) aab C) bba
4Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 010.
5.Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of 00.
6.Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of 1000.
7.Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of 110000.
8.Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A →0. Find a derivation of 01.
9.Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A →0. Find a derivation of 0011.
56.Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A →0. Find a derivation of 011111.
10.Let A = {0,11}. Find A2.
11. Construct a finite-state automaton that recognizes all strings that end with 11.