I'm currently enrolled to a CS course about programming languages and we learned about structural induction. In a question from our home assignments we need to proof that the following CFG has balanced parentheses:
My initial solution used simple induction and following the derivation rules of the CFG but the TA told us we need a stronger induction assumption that R has one more left parentheses than right parentheses. Can someone give me general direction to follow?
I'm assuming that the axiom is $E2$. By substituting $R$ in $E2$ you get the equivalent grammar: $$ E2 \to \varepsilon \mid \text{id} \mid () \mid (E2) $$
You can show by induction on the number $i$ of productions used that every sentential form of the above grammar has balanced parentheses.
The base case is $i=0$ and is trivial since $E2$ has no parentheses. For the inductive step notice that the only possible production replaces a single occurrence $E2$ with a sequence of symbols that has balanced parentheses. Therefore the resulting sentential form also has balanced parentheses.
We perform the induction on derivation steps. Let's say that our derivation of some sentence in $L(E2)$ is composed of $k$ steps, the first step is denoted as $V \xrightarrow{k} \alpha$, the second step (if $k >= 2$) will be $ \alpha \xrightarrow{k-1} \beta$, and so on. I'll be assuming that the starting symbol is $E2$
It's trivial that $E2 \xrightarrow{1} id | \epsilon $ lead to balanced parentheses. Also $E2 \xrightarrow{2} (R \xrightarrow{1} () $ is well balanced
So now we perform the inductive step for $k > 2$, with induction hypothesis that $E2 \xrightarrow{h} \cdots \xrightarrow{1} \alpha$ has well balanced parentheses for $h < k $. We must have the derivation steps $E2 \xrightarrow{k} (R \xrightarrow{k-1} (E2) \xrightarrow{k-2} \cdots \xrightarrow{1} (\alpha)$, where $\alpha$ will have balanced parantheses by induction hypothesis
