HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Chomsky normal form and regular languages

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#1525, answer score: 11

Revisions (0)

No revisions yet.