1
$\begingroup$

As we know, $\epsilon$ is the empty string, with length 0. It is not part of any any alphabet by default, unless specifically defined so. However, it is a string over any alphabet.

For example, Given that I need to design a Deterministic or Nondeterministic finite state automaton (without $\epsilon$ transitions) that accepts decimal numbers that are say, divisible by 2, would I have to account for the empty string as an input word as well? If so, how does divisibility work for null input?

$\endgroup$
2
$\begingroup$

The language has been defined as the set of strings that have some property. If the empty string has that property, then it is in the language. If the empty set does not have that property, then it is not in the language. It doesn't matter whether the property is "being a decimal representation of an even number" or anything else.

If the property is expressed in an imprecise or open-ended way that doesn't make it clear whether the empty string has the property or not, then you should choose whichever is most convenient for you and say what you have done.

$\endgroup$
2
$\begingroup$

It is rather standard to assume that 0 represents zero (and is divisible by two). Also it is usually assumed that decimal numbers do not start with 0.

I once presented a finite state automaton without these assumptions, where I took $\varepsilon$ as a representation for zero, and likewise 0000, and my students protested.

$\endgroup$
  • $\begingroup$ Ah. I see. So its basically upto me. Thank you! $\endgroup$ – Vishhvak Srinivasan Mar 2 '18 at 4:25
  • $\begingroup$ @VishhvakSrinivasan No, I am afraid the decision is to your professor :) $\endgroup$ – Hendrik Jan Mar 2 '18 at 15:58
2
$\begingroup$

The short answer is: no, you don't have to.

In the context of representations, the empty string is usually associated with the absence of representamen (that which might stand for something else). Technically, by definition, it could only represent itself, which is why we adopt a symbol from a meta-alphabet to denote it, when we have to.

In formal languages, it arises from the need to introduce the empty sequence as a legitimate word. For instance, it is the identity element of the concatenation operation, the complement of $\Sigma^+$, and so on.

That said, we could have a language for the representation of numbers on which the absence of representamen is equated to a value (zero, for instance). If your alphabet is unary, that would have to be the case. It wouldn't be properly a representation (except on the meta-alphabet). In some situations, what amounts to a value can still be produced by the absence of an event.

$\endgroup$
  • $\begingroup$ I see. I have a small clarification. Consider that a finite automaton has it's initial state as it's final state. Then, wouldn't all such automata technically accept $\epsilon$? In such case, in the problem of divisibility by 2, if I do happen to keep my initial state as my final state (in the case of say the initial state having input through a self loop - 0,2,4,6,8), my machine inevitably accepts null input right? The problem of deciding to take into account, or not taking it into account seemingly ceases to even exist in such case. $\endgroup$ – Vishhvak Srinivasan Mar 1 '18 at 20:24
  • $\begingroup$ You don't have to keep your initial state as a final state. If your alphabet has a symbol for zero, it will probably be a good idea to not accept $\epsilon$ in your language. $\endgroup$ – André Souza Lemos Mar 1 '18 at 21:46

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.