1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Word [()[] is not in $L$ since the no. of ( is not more than no. of ) in the prefix [(). $\endgroup$ – John L. Feb 22 '19 at 3:49
  • $\begingroup$ $S\to (S)S\mid\epsilon$ generates (), which is not in $L$. $\endgroup$ – John L. Feb 22 '19 at 3:50
1
$\begingroup$

The language is not context-free, as you have suspected.

Intuitively, a PDA that accepts the language has to keep track of the difference of the number of (s and the number of )s as well as the difference of number of [s and the number of ]s. Since these two differences vary to arbitrary largeness independently to each other, one pushdown stack is not able to track them. However, this understanding is not a rigorous proof.

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.

In case a more explicit hint is needed, here it is.

Check $(^{p+1}[^{p+1})^p]^p$ assuming the pumping length is $p$.

|cite|improve this answer
$\endgroup$

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.