So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would also be appreciated! As of now I'm just aware of it as a property, but I don't have a good grasp on why it is regular.

  • 1
    $\begingroup$ Any finite language is regular. $\endgroup$ Feb 12 '19 at 2:57
  • 2
    $\begingroup$ What is your definition of a regular language? If it is a language accepted by a DFA, then you can easily construct a DFA accepting $\{x\}$, which has $|x|+2$ states. It's a good exercise for you. $\endgroup$ Feb 12 '19 at 5:02
  • $\begingroup$ If your definition of regularity is based on regular expressions, then this is a very basic fact. Otherwise, this could be helpful. $\endgroup$
    – dkaeae
    Feb 12 '19 at 8:49
  • $\begingroup$ I thought x ∈ Σ* isn't assuming that x is finite? Like, x could be an infinitely large string. So {x} would be a single string with infinite length. $\endgroup$ Feb 12 '19 at 14:21

$\Sigma^*$ is a set of finite strings. There are infinitely many of them, but each one is finite – just like there are infinitely many natural numbers but each one of them is finite.

So, for any $x\in\Sigma^*$, $\{x\}$ is a finite language (it contains one string) of finite strings (because everything in $\Sigma^*$ is finite), so it's regular.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.