I'd love your help with the following question:

Let $G$ be context free grammar in the Chomksy normal form with $k$ variables.

Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ?

What is it about the amount of variables and the Chomsky normal form that is supposed to help me solve this question? I tried to look it up on the web, but besides information about the special form itself, I didn't find an answer to my question.

The answer for the question is that $B$ might be regular.

  • 1
    $\begingroup$ Indeed. The bits about Chomsky normal form and $K$ variables seem to be just distraction. But maybe there were more parts to the question? $\endgroup$
    – Tara B
    Commented Apr 27, 2012 at 13:17
  • $\begingroup$ I guess $B$ is regular if and only if $\mathcal{L}(G)$ is regular. $\endgroup$
    – Raphael
    Commented Apr 27, 2012 at 15:41

1 Answer 1


Assuming that $B$ is regular, then $L(G)=B \cup \lbrace w \in L(G) \mid \vert w \vert \leq 2^k \rbrace$ is also regular because the union of a finite number of regular languages is regular (especially, $k$ is a constant as the number of variables in the Chomsky normal form).

This can not be true in general because there are context free languages which are not regular.


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.