0
$\begingroup$

Hopcroft says it is a finite nonempty set of symbols.

$\varepsilon$ (empty string) is not an ordinary symbol.
$\mathbb{N}$ is not finite.
So, no to both?

On the other hand, I do not see why $\{\varepsilon\}$ cannot be an alphabet. Its Kleene closure is $\{\varepsilon\}$, so a language over this alphabet can be either $\{\varepsilon\}$ or $\emptyset$, both of which are valid languages.

For the alphabet $\mathbb{N}$, I have seen on Wikipedia that an alphabet can contain an infinite number of symbols, so which claim is true? Hopcroft or Wikipedia? Personally, I do not see why that would not work.

$\endgroup$
4
$\begingroup$

An alphabet can be any finite set of symbols. $\{\epsilon\}$ is a finite set of symbols so you can certainly use it as an alphabet. The strings over this alphabet are the empty string, $\epsilon$, $\epsilon\epsilon$, $\epsilon\epsilon\epsilon$, etc. Note that, in this context, we need some other notation for the empty string (some people use $\lambda$ for that anyway) and, in this context, $\epsilon$ does not denote the empty string: it denotes the one-character string whose only character is an epsilon. Likewise, $\epsilon\epsilon$ denotes the two-character string consisting of two epsilons.

Because it's confusing, we normally try to avoid having $\epsilon$ as a character in the alphabet. However, in some circumstances, it is a natural thing to do:

  • If you want to recognize languages of Greek words, it would be unnatural to use any alphabet other than the Greek one, $\{\alpha, \beta, \dots, \omega\}$ and that includes $\epsilon$.
  • If you want to write out a grammar for the strings that constitute valid regular expressions, e.g., over alphabet $\{0,1\}$, then you're going to need to use symbols $\{0,1,(,),+, {}^*, \epsilon,\emptyset\}$ (and life could get very confusing indeed).

So, if you want to stay sane, avoid having symbols such as $\epsilon$ in your alphabet as far as possible. But, if you can't avoid it, you just have to do it and use some other notation for the empty string.

$\mathbb{N}$ is not finite so it's normally not allowed as an alphabet, especially in the sort of formal language theory that's taught to undergraduates. It certainly makes sense to consider infinite alphabets in other contexts but, for most purposes, we stick to finite alphabets.

$\endgroup$
  • $\begingroup$ Maybe I wasn't clear in the first part of my question. Obviously, ε can be a part of the alphabet if it is understood as any other symbol like a,3,? or γ. However, if it is representing the entity of an empty string, then can it be an element of the alphabet set or not? I guess it cannot be, but I don't know exactly why. $\endgroup$ – waterlemon Oct 12 '18 at 14:18
  • 5
    $\begingroup$ If so, then the empty string itself would have infinitely many representation as a string of symbols: $\varepsilon$, $\varepsilon\varepsilon$, $\varepsilon\varepsilon\varepsilon$, etc. A character needs to be terminal and non-empty. $\endgroup$ – Thinh D. Nguyen Oct 12 '18 at 14:22
  • $\begingroup$ @ThinhD.Nguyen Got it. I was looking for these conditions. For some reason I just couldn't find them summarized in one place. $\endgroup$ – waterlemon Oct 12 '18 at 14:26
  • 2
    $\begingroup$ @ThinhD.Nguyen No! $\epsilon$ cannot simultaneously be a symbol in the alphabet and the notation for the empty string. If $\epsilon$ is in the alphabet, then $\epsilon\epsilon$ denotes the string consisting of two epsilons and does not have any other meaning. If $\epsilon$ is your notation for the empty string then it had better not be in the alphabet, and $\epsilon\epsilon$ is the empty string. $\endgroup$ – David Richerby Oct 12 '18 at 14:39

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.