patternMinor
Partitioning any language to regular?
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?
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.