Consider the following context-free grammar πΊ. πβππππ΄π΅π΄πππβ¦
GATE Β· 2026 Β· CS Β· Set 1 Β· Computer Science & IT
Consider the following context-free grammar πΊ.
πβππππ΄π΅π΄πππ
π΄βπππ΅π΅π΄π | ππ΅ππππ
π΅βππ΅π | ππ
In the above grammar, π is the start symbol, π and π are terminal symbols, and π΄ and B are non-terminal symbols.
Let πΏ(πΊ) be the language generated by the grammar πΊ. For a string π βπΏ(πΊ), let n1(π ) be the number of πβs in π and π2(π ) be the number of πβs in π .
Which of the following statements is/are true?
- A.
There is a string π βπΏ(πΊ) such that π1(π )<π2(π )
- B.
For every string π βπΏ(πΊ), π1(π )β₯π2(π )
- C.
There is a string π βπΏ(πΊ) such that π1(π )>2π2(π )
- D.
For every string π βπΏ(πΊ), π1(π )β€2π2(π )
Attempted by 45 students.
Sign up free to check your answer
Sign up freeLoading lessonβ¦