Problem Detail: I’m trying to solve this problem:
Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular
But can this be correct? If I have the language ${a}^*$ for example, that’s infinite but you can make a DFA for any sub-language of it, right? There’s a hint that this can be proved using diagonalization, but I think I must be misunderstanding the question.
Asked By : Þór Óðinsson
Answered By : muradin
Consider the language $L = {a^n mid n text{ is prime}}$. $L$ is a subset of ${a}^*!$, which is a regular language but it is not regular so has no DFA.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33189
