Deterministic finite automaton

A deterministic finite automaton (DEA, English deterministic finite state machine or deterministic finite automaton, DFA ) is a finite state machine by entering a character of its input alphabet ( the possible inputs ) from a state in which it is located, in a uniquely determined subsequent state changes. It differs from non-deterministic finite automaton whose state change does not always have to occur deterministically.

• 2.1 Vending Machine
• 2.2 Regular Expression

Definition

Machine

Formally, a DEA be defined as a quintuple. Where:

• Is a finite set of states. More often used symbols are for or.
• Is the finite input alphabet, ie, the set of allowed input symbols.
• Is the transfer function ( or transition function). It assigns to each pair consisting of a state and an input symbol a successor state to.
• Is the start state ( also the initial state or Initalzustand ).
• Is the set of accepting states, the so-called final states ( or final states ). Another common symbol is.

Behavior

The automaton is in a state and reads the input symbol, it changes to a new state, which is determined by the transition function, ie in the state.

If the machine still does not read input symbol, it is in the start state. Receives the automaton as input a sequence of input symbols, in theoretical computer science called word, it reads from left to right one symbol at a time and changes according to the transition function of the state. The machine is after reading the last input symbol in an accepting state, it accepts the input. We then say that the input word is in the set of words accepted by the automaton ( in short: the accepted by the machine language, see below).

Rejected entries

Ends of the machine according to the reading of an input word in a non- accepting state, the input is considered to be rejected. If the question is whether the entry is rejected or accepted, becomes clear not only from the last input symbol, a minimal automaton is prematurely in a state he does not leave.

Language of a DEA

The set of all words accepted by the DEA is referred to as the language of. The set of all languages ​​that are accepted by some DEA, is the class of regular languages ​​.

Nondeterministic finite automata ( NFA ), DEA and type-3 grammars ( in the Chomsky hierarchy ) describe the same class of languages ​​. NEA can be converted into equivalent DEA means power set construction.

Examples

Vending Machine

A deterministic finite automaton, the simple workings of a drinks machine replicates, may consist of the states which describe the following states of a drink machine: " Vending Machine is waiting for coin ", " Vending Machine waits for beverage choice " and " drink will be served ."

Valid input symbols could through the crowd, the insertion of a coin, describe the choice of a beverage Cancel the beverage choice and the extraction of a beverage.

An automaton with transitions

• ,
• ,
• And

Then describes that initially paid with a coin, then a drink is selected that has to be removed before it can be started again from the beginning. If you have inserted the coin, but not yet selected a drink, you can still abort.

If one demands for the transitions a total function, among other things, a condition must be specified in the machine changes from demolition when a drink has been selected but not yet taken.

The corresponding DEA with total transition function

Regular expression

The regular expression can be represented as the following DEA:

• Set of states
• Input alphabet
• Partial transition function with

Minimization

Each DEA exists (up to the designation of the states ) unique minimal automaton that accepts the same language.

Since the states of the minimal automata correspond to the equivalence classes of the language accepted by the finite automaton under the Nerode relation, one also speaks of equivalence class machine:

Be a deterministic finite automaton. Then with

The equivalence class machine to.

The minimization of deterministic automata can be algorithmically solved by continuous refinement of the equivalence classes. You start with the state quantities and. For each letter of the alphabet now every state set is divided to the effect that the transfer function of the states of each new amount reflects the letters in each one unique set. This is repeated until there is no more change.

There is also the opportunity to build minimal deterministic finite automata incrementally. Incremental means here that want to accept shall be added individually to the machine. After each insertion of such a word of deterministic finite automaton is minimal. This process is especially successful if the words often share common prefixes and suffixes, this is the case for example with words from natural languages.