What is finite automata 1

[Next] [Bottom of page] [Chapter] [Please report script error]

5.1. Finite automatons

5.1.1. Deterministic finite automata

Deterministic Finite Automata (DEA)

Idea of ​​the accepting deterministic finite automaton

A finite automaton is an (abstract) machine for character-by-character recognition of words in a regular language. It is in exactly one state after each processing step. At each step, a character is read and, based on the current status and the bookmark, a change is made to a successor status. When there are no more characters to be read and the machine is in an end state, the character string read is considered accepted. If no transition is possible with the symbol read, the character string to be processed is considered not to have been accepted. When reading in the first character of a character string, the machine is always in the so-called start state.

De fi nition 5.1.1 (DEA, deterministic fi nite state automaton).

A deterministic finite automaton A = 〈Φ, Σ, δ, S, F〉 consists of

  1. a finite set of states Zust
  2. a finite input alphabetΣ
  3. a (partial) state transition function δ: Φ × Σ → Φ
  4. a start state S ∈ Φ
  5. a set of final states F ⊆ Φ

Note

The transition function δ determines the subsequent state that is reached on the basis of the current state when reading a single character.

State transition diagram
It clearly shows an EA as a directed graph.

Example 5.1.2.

A = 〈{0,1}, {a, b}, δ, 0, {1}〉 with δ = {〈〈 0, a〉, 1〉, 〈〈 0, b〉, 1〉, 〈〈 1 , a〉, 1〉, 〈〈 1, b〉, 1〉}



Figure 5.1: State transition diagram

  • Every state is a knot.
  • The start state is marked with a free arrow or only with the label 0 (zero) or S (start).
  • Final states are framed twice.
  • Each state transition is a directed edge from the current state to the next state with the symbol as an edge label.
  • Alternative characters are often shown condensed with an arrow.

Partial state transition diagrams
The de fi nition of δ as a total function requires an edge for all states and signs from Σ. In linguistics, one often only shows nodes and edges that are relevant for the acceptance of a character string.

Example 5.1.3 (partial and complete automaton).

Error state and error transitions

To complete a partial transition diagram, add a state E.F to this, and make it the end node of all non-existent edges.

EA in XFST Prolog format

Example 5.1.4 (direct reading of EA in PROLOG format).

xfst [0]: read prolog
Type one or more networks in prolog format.
Use ^ D to terminate input.
arc (ex2,0,1, "a").
arc (ex2,1,2, "b").
final (ex2,2).

  • Edge representation: arc (NET, FROM, TO, CHARACTER)
  • 0 is the start state.
  • Final states: final (NET, STATE)
  • Writing EA Prolog format: write prolog> filename
    Short form wpl
  • Reading in from file: read prolog

Textual output from EA

Example 5.1.5 (display of information about the top EA on the stack).


xfst [1]: print net
Sigma: a b
Size: 2
Net: ex2
Flags: epsilon_free
Arity: 1
s0: a -> s1.
s1: b -> fs2.
fs2: (no arcs)
  • Sigma: List of all characters in the alphabet
  • Size: Number of edge labels
  • Net: name of the EA
  • Flags: important properties regarding ϵ, language size, I / O type, etc.
  • Arity: 1 = EA, 2 = transductor
  • States: s0: start state; for n> 0
    fsn: final state, sn: no final state
  • s1: b -> fs2 .: An edge labeled b goes from state s1 to the next state fs2.

5.1.2. Non-deterministic finite automata

Non-deterministic finite automaton (NEA)

Idea of ​​the accepting non-deterministic finite automaton

In contrast to the DEA, an NEA can change to more than one current state after each processing step. At each step, a character is also read and, based on the possible current states and the bookmark, a change is made to the permissible successor states.

Example evaluation
See Fig. 5.1.2 on page 87.


Figure 5.2: Example evaluation of the extended transition function for NEA

De fi nition 5.1.6 (NEA, non-deterministic fi nite state automaton).

A non-deterministic finite automaton A = 〈Φ, Σ, δ, S, F〉 differs from a DEA only in the transition function. You can move from the current state to any number of subsequent states with one sign.

Example 5.1.7 (table display and state diagram).

δ a b



s0 {s1, fs2} {fs2}
s1 {fs2}
fs2

Idea of ​​the accepting non-deterministic finite automaton with ϵ

As with the NEA, a character is read at each step and, based on the possible current states and the bookmark, a change is made to the permissible subsequent states.

However, the current states always include all states that are connected by any number of ϵ-transitions.

With a ϵ transition, no character is read.

De fi nition 5.1.8 (ϵ-NEA, non-deterministic fi nite state automaton).

A non-deterministic finite automaton with ϵ-transitionsA = 〈Φ, Σ, δ, S, F〉 differs from an NEA only in the transition function.

δ: Φ × (Σ∪ {ϵ}) → ℘ (Φ)

QUIZ Easy QUIZ on finite automata

[Next] [Top of page] [Supplementary chapter] [Please report script error]