- English only

# Lab for Automated Reasoning and Analysis LARA

# Finite state machine with epsilon transitions

#### Definition

Finite state machine with epsilon transitions is an extension of a finite state machine where transitions can be labelled by . If such a transition exists then an automaton may transition from to without consuming any portion of the input string.

As for finite state machine, we define a finite state machine with epsilon transitions as a 5-tuple with the only difference that where is a special symbol.

#### Execution of machine with epsilon transitions

An execution is now an alternating sequence of states and elements of . As before, an accepting execution starts from initial state and its last item is a final state. The word accepted by a given accepting execution is given by concatenating the labels of all transitions in an execution, with transitions ignored.

Note: we could further generalize to allow arbitrary strings

#### Eliminating epsilon transitions

Epsilon transitions are a matter of convenience and can always be eliminated by the following process. For each state we compute the set of all states reachable from along the edges with transitions. We then add the outgoing non-epsilon edges of all such to the existing outgoing edges of . We also insert into whenever one of the states is in . The resulting automaton accepts the same langauge and has no transitions.