GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 22

Question

Which of the following are context-free grammar for the language that contains all strings (including empty string) with matched parenthesis?

• A. $S \rightarrow (\; )$
  $S \rightarrow SS$
  $S \rightarrow (S)$
  $S \rightarrow \varepsilon$
• B. $S \rightarrow (\; )$
  $S \rightarrow SS$
  $S \rightarrow (S)$
• C. $S \rightarrow (\; )$
  $S \rightarrow SS$
  $S \rightarrow \varepsilon$
• D. $S \rightarrow (S )$
  $S \rightarrow SS$
  $S \rightarrow \varepsilon$

Answer 1

Starting symbol $\rightarrow S$

Non-terminal variables$ = \{(,)\}$

Production rules:

$S \rightarrow (\; )$
$S \rightarrow SS$
$S \rightarrow (S)$
$S \rightarrow \varepsilon$

Here, the first rule  is redundant as we can have it using rules $3$ and $4.$

Option B cannot generate empty string and option C cannot generate nested parenthesis.

So, the correct answer is A;D

Comments

I think that C is also correct as ()() is also balanced parenthesis. Kindly check this

---

@Sherrinford03 C cannot generate (())