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.
4
-
1$\begingroup$ Any finite language is regular. $\endgroup$– Derek Elkins left SECommented Feb 12, 2019 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 FilmusCommented Feb 12, 2019 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$– dkaeaeCommented Feb 12, 2019 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 SwansonCommented Feb 12, 2019 at 14:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
$\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.
answered Feb 12, 2019 at 14:45