[Solved]: Chomsky normal form and regular languages

Problem Detail: 

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.

Asked By : Jozef

Answered By : Marc Bury

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1525