The context free grammar given by \(S \rightarrow XYX \\ X \rightarrow aX \mid…
2015
The context free grammar given by
\(S \rightarrow XYX \\ X \rightarrow aX \mid bX \mid \lambda \\ Y \rightarrow bbb\)
generates the language which is defined by regular expression:
- A.
\((a+b)^*bbb\) - B.
\(abbb(a+b)^*\) - C.
\((a+b)^*(bbb)(a+b)^*\) - D.
\((a+b)(bbb)(a+b)^*\)
Attempted by 30 students.
Show answer & explanation
Correct answer: C
Final regular expression: (a+b)* bbb (a+b)*
Explanation:
The nonterminal X generates any string of a's and b's, including the empty string, so X corresponds to (a+b)*.
The nonterminal Y produces exactly the substring "bbb".
Since S -> X Y X, a derivation yields (string from X) + "bbb" + (string from X), which gives (a+b)* bbb (a+b)*.
Therefore the language is the set of all strings over {a,b} that contain the substring "bbb".