# Constructing CFG

How to generate CFG for this language?

$$L = \{ w \mid w \in \{ (, [, ], ) \}^* \text{ s.t. }$$

• In any prefix of $$w$$, no. of ( is more than no. of ), and
• no. of [ is more than no. of ].

$$\}$$

Thus, ([(), [()[] etc. are valid.

I have tried,

$$S \to (S \mid (S)S \mid [S \mid [S]S \mid \epsilon$$

But, this does not accept, ([)].

It seems possible to do with two stacks, by keeping counts of ( and [. Thus it seems it is not Context Free. Any help in proving it is not CF or a CFG exists?

• Word [()[] is not in $L$ since the no. of ( is not more than no. of ) in the prefix [(). – Apass.Jack Feb 22 at 3:49
• $S\to (S)S\mid\epsilon$ generates (), which is not in $L$. – Apass.Jack Feb 22 at 3:50

One standard way to disprove context-free-ness is to tap into the power of the pumping lemma. A bit of care should be taken to construct the witness word. For example, a word of the form $$(^{p+1})^p[^{p+1}]^p$$ or $$(^{p+1}[^{p+1}]^p)^p$$ can be pumped without any problem. However, that word is not far from the right word we need.
Check $$(^{p+1}[^{p+1})^p]^p$$ assuming the pumping length is $$p$$.