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

Is an infinite union of context-free languages always context-free?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
freelanguagesunioninfinitealwayscontext

Problem

Let $L_1$, $L_2$, $L_3$, $\dots$ be an infinite sequence of context-free languages, each of
which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $;
i.e., $L = L_1 \cup L_2 \cup L_3 \cup \dots $.

Is it always the case that $L$ is a context-free language?

Solution

The union of infinitely many context-free languages may not be context free. In fact, the union of infinitely many languages can be just about anything: let $L$ be a language, and define for every $l \in L$ the (finite) language $L_l = \{ l \}$. The union over all these languages is $L$. Finite languages are regular, but $L$ may not even be decidable (and thereby definitely not context-free).

The closure properties of context-free languages can be found on Wikipedia.

Context

StackExchange Computer Science Q#206, answer score: 21

Revisions (0)

No revisions yet.