5
$\begingroup$

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.

$\endgroup$
  • 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 Apr 27 '12 at 13:17
  • $\begingroup$ I guess $B$ is regular if and only if $\mathcal{L}(G)$ is regular. $\endgroup$ – Raphael Apr 27 '12 at 15:41
11
$\begingroup$

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.

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