0
$\begingroup$

Question: prove that the grammar $G = (\{S\}, \{(,)\}, R, S)$ where $R$ consists of three rules:

$S \rightarrow (S)~|~SS~|~\epsilon$

generates precisely all well-balanced parentheses.

I found a source where it used induction on the length of string and the length of CFG derivation.

First of all, it seems for the backward direction (all strings in the language are generated by $G$), they assumed $x$ is derivable from $G$ in the inductive hypothesis, then showed that $x$ is derivable from $G$. Is this prove valid? Shouldn't they show that all legal string of $|x|+1$ is derivable instead?

On the other hand, the proof seems more complicated than needed. Is it possible that there is a simpler proof in both directions?

Many thanks!

$\endgroup$

1 Answer 1

0
$\begingroup$

I didn't read the source you linked, but to prove that $G$ generates precisely all well-balanced parentheses you need to show two things:

  • all words $w$ with well balanced parenthesis are generated by $G$, and
  • all words $w$ generated by $G$ are well-balanced.

A grammar that needs to satisfy the first condition but not the second could simply generate $\{(,)\}^*$. A grammar that need to satisfy the second condition but not the first could simply generate the empty language.

In order to prove the former condition for you grammar you can proceed by induction on the length $|w|$ of $w$. The case $|w|=0$ is trivial since $\varepsilon \in L(G)$. For $|w| \ge 1$, notice that the first symbol of $w$ must be "(". Since $w$ is balanced we can write $w=(x)y$ where the ")" symbol is the paranthesis matching the first one, and $x$ and $y$ are (possibly empty) balanced words. Since $|x| < |w|$ and $|y| < |w|$ we can invoke the induction hypothesis twice to conclude that $x,y \in L(G)$, i.e., $S \rightsquigarrow x$ and $S \rightsquigarrow y$. Then $w \in L(G)$ by the following derivation $S \to SS \to ( S ) S \rightsquigarrow (x)y$.

For the latter condition, you can prove that all parentheses in any sentential forms $\alpha$ of $G$ are well-balanced. The proof is by induction on the number of applied productions. If no productions are applied then $\alpha = S$, which contains no parentheses and hence its balanced. Otherwise consider the last applied production. The only production that involves parentheses is $S \to (S)$. Before applying this production, the sentential form was balanced by induction hypothesis and the production $S \to (S)$ keeps the sentential form balanced.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.