1
$\begingroup$

I am not sure about the answer. Intuitivly I would say that there are alphabets for which there are no non-regular languages. In particular I am thinking of languages with only one element. But I am not sure.

$\endgroup$
4
  • 1
    $\begingroup$ Some intuition: an automaton cannot really "count". It can essentially only count modulo some fixed number. So over a singleton alphabet, try taking some language with very large "gaps". For example, the language of words of length $2^n$ for some $n$. $\endgroup$ – Shaull Dec 3 '20 at 10:57
  • $\begingroup$ Over an alphabet with one character, suppose that the language consists of words such that the length increases very fast. This would make the condition in the pumping lemma to not hold since it requires the existence of words with lengths that form an arithmetic progression. $\endgroup$ – plop Dec 3 '20 at 10:57
  • $\begingroup$ There are uncountable many languages over $\{0\}$, but only countably many regular languages. $\endgroup$ – Yuval Filmus Dec 3 '20 at 11:29
  • $\begingroup$ We can actually describe explicitly all regular languages over $\{0\}$. The idea is to consider a DFA over $\{0\}$. After removing all unreachable states, we are left with a path leading to a cycle. This leads to an explicit description. $\endgroup$ – Yuval Filmus Dec 3 '20 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.