Consider a context-free grammar 𝐺 with the following 3 rules. 𝑆 β†’ π‘Žπ‘†, 𝑆 →…

GATE Β· 2024 Β· CS Β· Set 2 Β· Computer Science & IT

Consider a context-free grammar 𝐺 with the following 3 rules.

        𝑆 β†’ π‘Žπ‘†, 𝑆 β†’ π‘Žπ‘†π‘π‘†, 𝑆 β†’ 𝑐

Let 𝑀 ∈ 𝐿(𝐺). Let π‘›π‘Žπ‘›_π‘Ž (𝑀),𝑛𝑏 𝑛_𝑏 (𝑀), 𝑛𝑐𝑛_𝑐 (𝑀) denote the number of times π‘Ž, 𝑏, 𝑐 occur in 𝑀, respectively. Which of the following statements is/are TRUE?

  1. A.

    π‘›π‘Ž(𝑀) > 𝑛𝑏(𝑀)

  2. B.

    π‘›π‘Ž(𝑀) > 𝑛𝑐 (𝑀) βˆ’ 2

  3. C.

    𝑛𝑐(𝑀) = 𝑛𝑏(𝑀) + 1

  4. D.

    𝑛𝑐(𝑀) = 𝑛𝑏(𝑀) βˆ— 2

Attempted by 108 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…