Skip to main content
added 7 characters in body
Source Link
Steven
  • 29.6k
  • 2
  • 28
  • 49

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$ (this is easy to show by induction), 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 oneproduction 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.

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$ (this is easy to show by induction), 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 one 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.

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.

Source Link
Steven
  • 29.6k
  • 2
  • 28
  • 49

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$ (this is easy to show by induction), 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 one 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.