In
computer science, when dealing with
finite automata and
regular expressions, epsilon (ε) is used to denote "the
empty string". It should be noted that ε,
∅, and {ε} are all different things (this is a common mistake made by beginning CS students). ε is of type "
string", whereas ∅ and {ε} are of type
"set of strings"; ∅ does not contain ε, whereas {ε} (obviously) does. However, ∅* is equivalent to ε. ε is the
identity for
concatenation:
εR ≡ Rε ≡ R
Regular expressions in UNIX have extended operations beyond the basic three (union, concatenation, and closure); however, they can all be represented by standard regular
expressions. The '?' operation in UNIX regular expressions stands for 'zero or one occurrences of'; i.e., R? is the same as (R | ε).
In a finite automaton, a transition on ε means the automaton moves from one state to another without consuming a character; automatons with epsilon-transitions are one type of non-deterministic finite automaton. Epsilon-transitions are necessary to convert regular expressions into finite automata.