Question

The context free grammar S → A111|S1, A → A0 | 00 is equivalent to _________

(a) {0^n1^m | n=2, m=3}

(b) {0^n1^m | n=1, m=5}

(c) {0^n1^m | n should be greater than two and m should be greater than four}

(d) None of the mentioned

This question was posed to me during an internship interview.

Query is from Context Free Grammar topic in portion Contextfree Grammar and Syntax Analysis of Compiler

Answer 1

Right choice is (a) {0^n1^m | n=2, m=3}

Easy explanation: S-> A111

     S->00111 (A->00).