Here is a context-free grammar G:

S → AB

A → 0A1 | 2

B → 1B | 3A

Which of the following strings is in L(G)?

a) 0002111112

b) 21113021

c) 021131021

d) 00021132

Would you help me to get the answer?

## Expert Answer

B) True

C)False

D) False

**Explanation Below.**

a) 0002111112, is not in L(G) , because for a string to be in L(G) it must contain at least one “3” , because String can terminate only from A . so B->3A rule must be applied once. here there is no “3” in this string so this string is

B) Explanation provided in image

C) This is not in L(G) because from the Rule after 3 either 0 can come or 2 can come becasue A starts with either “0” or “1” , in this example after 3 it is “1” which is vioilating the rule.

D) This is not in L(G) because In this language no of 0’s can not be greater than no of 1’s because of rule 0A1 which says no of 0’s are equal to number of 1’s but we have other rules for 1’s also like B->1B , so to satisfy the language crierial no of 1’s must be greater than number of 0’s.