I know what reflexive and transitive closure is but I am not able to figure out what is going in the following proof in Book Theory Of Computation Its a bit long so please bare with me. Before down voting (in case) please state the reason behind it, It took me an hour to write and format the question as best as I could. However I am ready to make corrections if any. Thanks in advance. So here goes the question -
Consider the following CFG, G = (N,T,P,S), N = {S,A,B}, T = {a,b}. P consists of the following productions.
- S $\rightarrow$ aB
- B $\rightarrow$ b
- B $\rightarrow$ bS
- S $\rightarrow$ aBB
- S $\rightarrow$ bA
- A $\rightarrow$ a
- A $\rightarrow$ aS
- A $\rightarrow$ bAA
The language generated by the grammar above consists of strings having equal nos of a's and b's.
Next they use induction to prove the last line above.
Induction Hypothesis
- S $\overset{*}{\Rightarrow}$ w if and only if w has equal number of a's and b's.
- A $\overset{*}{\Rightarrow}$ w if and only if w has one more a than, it has b's.
- B $\overset{*}{\Rightarrow}$ w if and only if w has one more b than, it has a's.
And so on.....
Here $\overset{*}{\Rightarrow}$ means the - Reflexive, transitive closure of $\Rightarrow$
Which comes from the previous text
If $\alpha_1 \Rightarrow \alpha_2, \alpha_2 \Rightarrow \alpha_3,...., \alpha_{n-1} \Rightarrow \alpha_n$, the derivation is denoted as $\alpha_1 \Rightarrow \alpha_2 \Rightarrow .... \Rightarrow \alpha_n$ or $\alpha_1 \overset{*}{\Rightarrow} \alpha_n$, where $\overset{*}{\Rightarrow}$ is reflexive, transitive closure of $\Rightarrow$.
And the definition
The language generated by a grammar G =(N,T,P,S) is the set of terminal strings derivable in the grammar from the start symbol.
L(G) = {$w|w \in T^*, S \overset{*}{\Rightarrow} w$}
So my question here is
- What does $S \overset{*}{\Rightarrow} w$ means or what does it actually convey.
- So my second question is that in the above induction hypothesis I got 1st hypothesis that I have to show that the S derives equal nos of a's and b's but what does 2 & 3 means? I am not able to get why 2 and 3 have been taken and what does they signify?
$\Rightarrow$ is the one-step derivation relation. This means that the string on the left-hand side can be converted to the string on the right-hand side by one application of one rule.
The transitive and reflexive closure pairs all strings such that the one on the left-hand side can be converted to the string on the right-hand side by zero (reflexive) or more (transitive) applications of rules.
Concerning the second part: It is not clear from your summary of the proof. In principle is is sufficient to show the claim for S. Maybe the ones for A and B are used in this proof.