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

Partitioning any language to regular?

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

Problem

One time I saw a theorem that says something like any language can be partitioned into regular languages, but I can't remember exactly what the theorem is.
Could somebody tell me, is this true? What is this theorem?

Solution

Every language can be partitioned into a countable union of singleton languages (languages of the form $\{w\}$). Since singleton languages are regular, we get that every language can be partitioned into infinitely many regular languages.

Context

StackExchange Computer Science Q#49512, answer score: 5

Revisions (0)

No revisions yet.