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.