Question

I have 3 grammars

A -

S→ a T ∣ S b ∣ ϵ

T→ Sb ∣ b

B -

S→ ϵ ∣ aSb ∣ aSbb

C-

S→T ∣ a S b b

T→ ϵ ∣ a T b

Find me the sublanguage relation

e.g [(A,A) ,(B,B),(C,C), ...... ]

Answer 1

Solutions :

Note : ^ is used as power in expressions .

A) 

S -> aT | Sb | ϵ
T -> sb | b 


The strings  generated by the above grammar  are : 

str={ ϵ, b , b^2,b^3 ,_ _ _ _, __,
      ab , ab^2 , ab^3 < _ _ _ _ ,  _ _ ,
      a^2b^2 , a^3b^3, a^4b^4 , _ _ _ _ ,  
      a^2b^3,a^2b^4, _ _ _ _ , __ } 


we can conclude that 

L(G) = {a^m b^n , n>=m  }   

B) 

 S→ ϵ ∣ aSb ∣ aSbb

Strings genrated by the given grammer can be 

str={ϵ , ab , a^2b^2 , a^3b^3 ,_ _ _ _ _ _ _ _ _ ,a^2b^3 , a^2b^4 , a^3b^4 a^3b^5 ,a^3b^6 , a^4b^5,
     a^4b^6,a4^b^7 _ _ _ _ _ } 


from observation it can concluded that , 

Genrated grammer can be : 

L(G) ={a^m b^n , m<=n<=2*m } 

This grammar  generates all the strings such that n lies between m and 2 * m as shown in above grammer.

C) 

S→T ∣ a S b b
T→ ϵ ∣ a T b


Strings generated by the above grammar as follows : 

str={ϵ , ab , a^2b^2, a^3b^3 , _ _ _ _ _ _ _ , _ _  
      ab^2,a^2b^4 , a^3b^6 ,_ _ _ _ _ _ _ _ , _ _ 
       a^2b^3 , a^3b^4 , a^4b^5,_ _ _ _ __ , _ _ } 

from above set of stirngs we can conclude that 

L(G) = { a^m b^n , m=n or n=2*m or n=m+1 except when m=0 }