1
$\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
  • $\begingroup$ 1. For the future readers reading this question, OP may mean we should derive $x=[z]$ from the assumption of $z$ instead of the converse direction in the reference lecture p36 where 'o/w' may mean otherwise. 2. If someone is interested about this QA, this similar SO QA may be helpful which uses one more simpler grammar. $\endgroup$
    – An5Drama
    Apr 11 at 7:51

1 Answer 1

2
$\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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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