Q29: Context free grammar example

Question #29:

Following productions represent the context free grammar, where E is the start symbol and {0, 1, a, b} represent the terminal symbols.

What is the language of the variable I?

 

Options:

A)     I represents the regular language of the form (a + b)(a + b + 0 + 1)*

B)      I represents the regular language of the form (a + b + 0 + 1)*(a + b)

C)      I represents the context free language of the form a(a + b + 0 + 1)*a + b(a + b + 0 + 1)*b

D)     I represents the context free language of strings of the form of palindrome.

 

Solution:

Since the first symbol is I in the productions 7, 8, 9 and 10, and I can only be reduced to a or b, hence the final strings that are accepted must start with a or b. Hence, the correct answer is A.