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

Asked By : Dave

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32334

3.2K people like this

 Download Related Notes/Documents