PLC with empty transition

Difficulty

Easy 25%

Contents

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 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 PLC with empty transition to recognized words

The process is the same as the tree created by a non-deterministic automaton. Let us note that in addition to having to create new branches in the event of indeterminism, it is also necessary to go through the transitions of the successor states by epsilon-transition.

If we take the above automaton 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 a PLC with epsilon transition, it is then necessary to close the PLC.

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 the cases where several epsilon-transitions follow one another and if they go into a final state, but the general principle presented here remains valid (it is enough to apply the first step).