Automaton with epsilon transition

Automata are drawn by displaying the states by circles, indicating the initial state by an incoming arrow, the accepting states by a double circle or an outgoing arrow, and the transition from the state q to the state q’ by reading the letter α by an arrow going from q to q’ and labeled by α.

A finite state automaton A with epsilon transition (or 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 application called the 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 then there will be a single transition, or as a word, and there can then be an arbitrary number of transitions (of which at most one will be non-empty).

Again, the notions of derivation are unchanged, and that of derivation tree only requires a trivial adaptation, because there are now transitions labeled by ε. The calculations of a antomaton with empty transitions allow the passage through any number of empty transitions during execution. The number of states traveled will therefore no longer equal the number of letters of the input word but may be much larger. The derivation 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 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 indeterminacy, it is also necessary to traverse the transitions of the successor states by epsilon-transition.

The principle of the algorithm is to replace each path of length 1 starting with an epsilon-transition with a new transition that describes this path.

langage13

There are two path of length 1 that start with the epsilon transition:

  • (1, ε, 3)(3, b, 3)
  •  (1, ε, 3)(3, c, 4)

Two new transitions are added to the automaton that summarize these two paths:

  • (1, b, 3)
  • (1, c, 4)

And we delete the transition (1, ε, 3).

langage14

The algorithm is a little more complex in cases where several epsilon-transitions follow each other and if they go into a final state, but the general principle presented here remains valid (just apply the first step many times).

 

Publicités