0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Any finite language is regular. $\endgroup$ – Derek Elkins Feb 12 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$ – Yuval Filmus Feb 12 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 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$ – James Swanson Feb 12 at 14:21
1
$\begingroup$

$\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.

$\endgroup$

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.