1
$\begingroup$

Can epsilon be in the input alphabet of an FST ?

$\endgroup$
  • 1
    $\begingroup$ Have you checked the definition? $\endgroup$ – Raphael Nov 2 '17 at 21:15
4
$\begingroup$

The alphabet $\Sigma$ of an automaton can be any nonempty set of finite symbols. Surely Greek-speakers would be upset if we forbade $\{\alpha, \beta, \dots, \epsilon, \dots, \omega\}$ as a valid alphabet! If you want, you can use $\{\clubsuit,\diamondsuit,\heartsuit,\spadesuit\}$ as your alphabet. Or $\{A, \alpha, \clubsuit,8\}$. Or any other finite, nonempty set.

However, certain symbols have special meanings and we tend not to use them in automaton alphabets. For example, if you want your alphabet to consist of the symbols $\}$ and $\{$, things get a bit awkward: you start writing $\Sigma = \{\},\{\}$ and, er, yeah, that doesn't quite work. Likewise, it's confusing if $\Sigma$ contains symbols such as ${}^*$, $($, $)$, $+$ and so on: you can easily write $\Sigma = \{{}^*, (, ), +\}$ but, now, when you try to write regular expressions over that alphabet, it's impossible to tell which characters in the regular expression are symbols from $\Sigma$ and which are operators in the regular expression.

$\epsilon$ fits into this second class. When $\epsilon$ isn't in the alphabet, we use that symbol to denote the empty string. As such, if you include $\epsilon\in\Sigma$, it becomes unclear whether writing "$\epsilon$" means "the empty string" or "the string containing one symbol, which is the Greek equivalent of 'e'". So, as a practical matter, we usually prefer not to use $\epsilon$ as a symbol in the alphabet. If you do need to include $\epsilon$ in your alphabet, you should use some other symbol to denote the empty string and you should say so. Similar reasoning applies to all other symbols that could be confused in this and other ways.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ We indeed cannot use epsilon as a part of input alphabet after we agree upon to use it to denote the empty string. Should we use lambda instead of epsilon to denote the empty string epsilon clearly could be used as a part of input alphabet. But the asker asks the question assuming that epsilon is already used to denote the empty string. He/she knows that epsilon has a special meaning and hence confused. A brief answer epsilon is a string and so not a symbol. It something like a number cannot be a digit while digits form numbers. $\endgroup$ – fade2black Nov 3 '17 at 11:15
  • $\begingroup$ So your post does not answer the question. $\endgroup$ – fade2black Nov 3 '17 at 11:17
  • 3
    $\begingroup$ @fade2black I'm sorry, but your claim that I've not answered the question is nonsensical. "But the asker asks the question assuming that epsilon is already used to denote the empty string." Sorry but the question says no such thing. That is your assumption. $\endgroup$ – David Richerby Nov 3 '17 at 11:27
  • 1
    $\begingroup$ When the conflict occurs, some kind of escape sequence is given to disambiguate and the problem is resolved. $\epsilon$ vs \ $\epsilon$. At least seen in Formal Languages and Automata Theory. $\endgroup$ – Evil Nov 3 '17 at 11:43
-1
$\begingroup$

Basically, the epsilon (denoted by $\epsilon$) is a string, namely empty string (altrenatively denoted by $\lambda$) cannot be a part of an alphabet since a string itself consists of finite sequence of elements of the alphabet, i.e., symbols. Empty string is a string of length zero and so it is not a symbol by definition.

Furthermore, by the formal definition of finite automata, the input alphabet is defined as a finite set of symbols, i.e., not strings and hence the empty string cannot be an input symbol.

However, epsilon is allowed as a part of the input in generalization of NFA, called NFA with $\epsilon$-moves. In this case the transition function is defined as a function from $\Sigma \cup \{\epsilon\}$ into $2^Q$. But epsilon is still not a member of alphabet it is just a part of definition of the transition function.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ "epsilon (denoted by $\epsilon$ or $\lambda$)" Er, if it's denoted by $\lambda$, then it's lambda, not epsilon. More seriously, this answer is just wrong. The alphabet is a set of symbols. $\epsilon$ is a symbol. There is no mathematical reason why you can't have $\epsilon\in\Sigma$. And $\epsilon$ is not part of the input in an $\epsilon$-NFA! $\epsilon$-NFAs are allowed to change state without reading inputs but the input to an $\epsilon$-NFA is a string in $\Sigma^*$. Since you've forbidden $\epsilon\in\Sigma$, you can't have $\epsilon$s in the input. $\endgroup$ – David Richerby Nov 3 '17 at 10:39
  • $\begingroup$ @DavidRicherby You restate the same thing what I wrote. My answer is that epsilon is not a part of alphabet. What part is wrong? $\endgroup$ – fade2black Nov 3 '17 at 10:50
  • 3
    $\begingroup$ Essentially all of it is wrong. Your claim that epsilon can be denoted by $\lambda$ is wrong. Your claim that $\epsilon$ can only denote a string is wrong. Your claim that $\epsilon$ is not a symbol is wrong. Your claim that the input of an $\epsilon$-NFA can include $\epsilon$s when $\epsilon\notin\Sigma$ is wrong. $\endgroup$ – David Richerby Nov 3 '17 at 10:52
  • $\begingroup$ @DavidRicherby empty string for example in Sipser's book is denoted by lambda. Wrong? $\endgroup$ – fade2black Nov 3 '17 at 10:54
  • 4
    $\begingroup$ Denoting the empty string by $\lambda$ is fine. But you claimed that we can denote the Greek letter epsilon by the Greek letter lambda and that is complete nonsense. That wasn't really a serious problem, but the other things I've mentioned are serious. $\endgroup$ – David Richerby Nov 3 '17 at 10:56

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.