last two days I am trying to prove, that Dyck language $L$ over the alphabet $\{[, ]\}$ is a subset of the language $L(G)$ generated by the grammar with rules $\{S \rightarrow [S]S | \epsilon \}$.
Recommended steps by our lector are:
a) Prove that every nonepmty $w \in L$ can be written as $w = [u]v$, where $u,v$ $\in$ $L$
b) prove with induction where i is number of '[' in $w$ that L $\subseteq$ L(G), use a) in induction step
Thanks for any advice.
Edit: I have solved the problem from a, but I do not know, if its valid proof and how to solve b.
a) Prove that every nonepmty $w \in L$ can be written as $w = [u]v$, where $u,v$ $\in$ $L$:
- $D = ( \{S'\}, \{[, ]\}, \{ S \rightarrow S'S' | [S'] | \epsilon \}, S' )$ is a grammer defining Dyck language over alphabet $\{[,]\}$.
- The only way to create $w \in L$ where $|w| > 0$ is to apply rule $\{S'\rightarrow[S'] \}$ at least once.
- $w_1$: $S' \rightarrow [S'] \rightarrow^* w_1 $
- $w_2$: $S \rightarrow S'S' \rightarrow^* S^i[S']S^j \rightarrow^* w_2 $ where $i, j \geq 0$
- In 3rd case, $w = [u]v$, where $v = \epsilon$ and $u$ is generated from starting symbol, so $u, v \in L$. In 4th case, you have $w = [u]v$ where $u, v$ is generated from starting symbol $S'$ so $u, v \in L$