Consider a context-free grammar G with the following 3 rules. S aS, S aSbS, S c Let w ∈ L(G). Let n_a(w), n_b(w), n_c(w) denote the number of times a, b, c occur in w, respectively. Which of the following statements is/are TRUE?

GATE CSE 2024 Session 2 Q52: Symbol-count relations for S → aS | aSbS | c

Theory of Computation
2 marks
MSQ
No negative marking

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

$S \to aS, \quad S \to aSbS, \quad S \to c$

Let $w \in L(G)$ . Let $n_a(w), n_b(w), n_c(w)$ denote the number of times $a, b, c$ occur in $w$ , respectively. Which of the following statements is/are TRUE?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: B, C (official GATE 2024 final answer key)

Concept used: Track how each rule changes the counts of $a$ , $b$ , $c$ and the number of pending $S$ .

First step: Each $aSbS$ adds one $a$ , one $b$ and one extra $S$ ; each $S$ finally becomes one $c$ . Check (A) on $w = c$ .

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2024 Session 2 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2024 Session 2 questions →

GATE CSE 2024 Session 2 Q52: Symbol-count relations for S → aS | aSbS | c

Question

Full step-by-step solution

More Theory of Computation PYQs