Consider the context-free grammer G below. There S is the starting non…
2023
Consider the context-free grammer G below. There S is the starting non terminal symbol, while a and b are terminal symbols.
S→aaSb|T
T→Tb|a
Which of the following statments is true about the language L(G) generated by G?
- A.
aabbaabb belongs to L(G) but aabb does not
- B.
aaaaabbb belongs to L(G) but aaaabb does not
- C.
aaaabb belongs to L(G) but aabbaabb does not
- D.
aaabb belongs to L(G) but aaaaabbb does not
Attempted by 22 students.
Show answer & explanation
Correct answer: B
First, analyze the non-terminal T. The rule T→Tb|a generates strings of the form ab^k where k≥0. Next, analyze S. The rule S→aaSb|T implies that for every application of the first rule, two 'a's are added to the front and one 'b' is added to the back. If T is reached after n applications of S→aaSb, we get a^{2n}Tb^n. Substituting T gives a^{2n+1}b^{k+n}. Thus, the number of 'a's is always odd (2n+1), and the number of 'b's is at least n. For Option B, aaaaabbb has 5 'a's (n=2) and 3 'b's. Since 3≥2, it is valid. Options with even 'a's are invalid.