patternModerate
Chomsky normal form and regular languages
Viewed 0 times
languageschomskyregularnormalandform
Problem
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.
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.
Solution
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.
This can not be true in general because there are context free languages which are not regular.
Context
StackExchange Computer Science Q#1525, answer score: 11
Revisions (0)
No revisions yet.