Consider the language $L$ over the alphabet (,[,),] such that any word $w \in L$ if formed as a shuffle of two (possible empty) well-formed sequence of parenthesis: one over (,) and another over [,]. Examples:

$$()[\,] \in L;$$ $$(()[\,]) \in L;$$ $$([)] \in L;$$ $$[(][)] \in L;$$ $$[(][([)(])]) \in L.$$

It is well-known that no context-free grammar exist for this language. Do you know how to write a context-sensitive grammar for $L$?.

I know how to recognize the words from $L$ using a certain pushdown automaton with 2 stacks. But, in general, such automatons are more strong than context-sensitive grammars.


1 Answer 1


Basically, the idea is that $($ and $)$ can commute with $[$ and $]$, but $($ cannot commute with $)$ – and same for $[$ and $]$.

An essentially noncontracting grammar would be:

$S \to \varepsilon \mid S'$

$S' \to S'S'\mid A_1S'B_1 \mid A_2 S' B_2 \mid A_1B_1 \mid A_2 B_2$

$A_1 \to \, ($

$B_1 \to \, )$

$A_2 \to \, [$

$B_2 \to \, ]$

$A_1A_2 \to A_2A_1$

$A_1B_2 \to B_2A_1$

(remaining rules are the same thing for $B_1A_2$, $B_1B_2$, $A_2A_1$, $A_2B_1$, $B_2A_1$, $B_2B_1$).

  • $\begingroup$ Merci @Nathaniel, I see the idea, actually, commuting does the thing. $\endgroup$
    – kerzol
    Commented Apr 13 at 22:25
  • 2
    $\begingroup$ Plus the nesting $S'\to A_i S'B_i$. $\endgroup$ Commented Apr 13 at 23:37
  • 1
    $\begingroup$ @HendrikJan Of course! I had forgotten these rules. Thanks for noticing. $\endgroup$
    – Nathaniel
    Commented Apr 14 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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