3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Dave Oct 26 '14 at 18:18
  • 1
    $\begingroup$ @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$. $\endgroup$ – Rick Decker Oct 26 '14 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.