Phrase-structure grammar

[alexriverajr]

Let G=(V,T,S,P) be the phrase-structure grammar with V={0,1,A,B,S}, T={0,1} and set of productions P consisting of S -> 0A, S-> 1B, A -> 010A, B -> 00B, A -> 0 and B -> 1. Show that “100001” and “00100” belong to the language generated by G.

 

[daon]

"100001" = S->1B->100B->10000B->100001
"00100" = S->0A->0010A->00100