Cheap and Secure Web Hosting Provider : See Now

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

, ,
Problem Detail:

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.

#### Answered By : Rick Decker

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$.