Question

Here is a context-free grammar G: S → AB A → 0A1 | 2 B → 1B | 3A which of the following strings are in L (G)?

(a) 021300211

(b) 022111300211

(c) None of the mentioned

(d) 021300211 & 022111300211

This question was addressed to me during an internship interview.

My question is based upon The NFA with n-moves to the DFA in portion Finite Automata and Regular Expression of Compiler

Answer 1

Correct option is (d) 021300211 & 022111300211

The best explanation: First, notice that A generates strings of the form 021, where n is 0 or more. Also, B gives zero or more 1’s, which is followed by one 3, and then A gives something. Since S generates something an A can generate followed by something a B can generate, the strings in L (G) are of the form 0 21 30 21.