PLC with empty transition
We are used to drawing a automaton with empty transition, by representing the states by circles, by indicating the initial state by an incoming arrow, the accepting states by a double circle or an outgoing arrow, and the transition from state q to state q' by reading the letter α by an arrow going from q to q' and labeled by α.
A finite automaton A with epsilon transition (or automaton with empty transition) is a triplet (Vt, Q, T) where
- Vt is the vocabulary of the automaton;
- Q is the finite set of states of the automaton;
- T: Q × (Vt ∪ ε) → Q, is a partial map called the automaton transition function.
Note that the notation q(α)→q' becomes ambiguous, since it now takes on two different meanings depending on whether α is considered as a letter (or as the symbol ε) and there will then be a single transition, or as a word (of length 1 or 0), and there can then be an arbitrary number of transitions (of which at most one will be non-empty).
Again, the notions of derivation is unchanged, and that of derivation tree
requires only a trivial adaptation, since there are now transitions labeled by ε. The calculations of an automaton with empty transitions allow the passage through any number of empty transitions during execution. The number of states scanned will therefore no longer be equal to the number of letters in the input word but may be much greater. The calculation tree of an automaton with empty transitions turns out to be a less interesting tool than for non-deterministic automata without empty transitions.
From automaton with empty transition to recognized words
The process is the same as the tree created by a non-deterministic automaton. Note that in addition to having to create new branches in case of indeterminism, it is also necessary to traverse the transitions of the successor states by epsilon-transition.
If we take the automaton above on the word aaaab:
p(aaaab) → q(aaab)→r(aaab)→s(aaab)→s(aab)→s(ab)→s(b)→q(b)→r – terminal state
It is complex to calculate the words of length n recognized by an automaton with epsilon transition, it is then necessary to close the automaton.
The principle of the algorithm consists in replacing each path of length 1 starting with an epsilon-transition by a new transition which describes this path.
There are two paths of length 1 which start with the transition on epsilon:
- (1, ε, 3) (3, b, 3)
- (1, ε, 3) (3, c, 4)
We add to the automaton two new transitions which summarize these two paths:
- (1, b, 3)
- (1, c, 4)
And we remove the transition (1, ε, 3).
The algorithm is a little more complex in cases where several epsilon-transitions follow each other and if they go to an end state, but the general principle presented here remains valid (just apply the first step).