# Show that the string $( [ ) ]$ is not in a Dyck language

I think I understand why the string $( [ ) ]$ is not in a Dyck language.

In my words,

D2* is all the dyck words of 2 parentheses.

From the definiton of $D2*$, every words must have exactly 2 pairs correctly nested pairs of parentheses.

All the words of the language are given by

$\sum = { (1, )1, (2, )2 }$

The alphabet consisting of 2 kinds of left and right parentheses.

The language is given by the following grammar :

1. Terminal set is $\sum$

2. Start variable is not in terminal set

3. $S -> \big( \epsilon | SS | (i S )i \big)$ for all i > 1

But the form of that word is $(i (j )i )j$ which fails to match the definition.

But I'm having trouble writing a formal proof on that.

• What exactly do you mean by $([)]$? The finite language consisting of one string exactly, namely $([)]$? And what's $D2*$? Oct 26 '14 at 15:42
• ([)] is a string
– Dave
Oct 26 '14 at 15:50

Consider producing a leftmost derivation of ( [ ) ]. We can begin with $$S\Rightarrow SS\stackrel{*}{\Rightarrow}SS\dotsc S$$ and to get the ( on the left we must eventually use the production $S\rightarrow(S)$ on the leftmost $S$, giving $$S\stackrel{*}{\Rightarrow}(S)S\dotsc S$$ and then we'll have $$S\stackrel{*}{\Rightarrow}(SS\dotsc S)S\dotsc S$$ and to get the [ as the second terminal on the left we must eventually use the production $S\rightarrow[S]$, giving $$S\stackrel{*}{\Rightarrow}([S]SS\dotsc S)S\dotsc S\stackrel{*}{\Rightarrow}([SS\dotsc S]SS\dotsc S)S\dotsc S$$ and now we're stuck, since no production will give us the ) terminal we need on the left without introducing a ( first.
For a slightly different take, consider that $S$ can only derive strings in $D_2$, so to derive ( ] ) ] we must use the production $S\rightarrow (S)$, where the $S$ in the right term of the production must also derive a string in $D_2$, but that would imply $S$ derives ], which cannot be, since $]\notin D_2$.
• Thanks Rick. Just a quick question. Am I right to add the following conclusion : By construction, it is impossible to derive $([)]$ with the grammar G1. My question is, is this considered a construction proof ? Or is it a contradiction proof ?
• @Dave. You're right about the conclusion. As to what I'd call the proof technique, I suppose I'd call it a proof by construction (i.e., that the string cannot be derived from the grammar), although one could call it a proof by contradiction, namely that by assuming that we could derive the string (namely that ( ] ) ] was in $D_2$), we reach the contradiction that ( ] ) ] was not in $D_2$. Oct 26 '14 at 20:15