Automata - Deterministic finite-state automata (DFA)

About

A Deterministic finite-state automata (DFA) is a finite automaton that cannot be in more than one state at any one time.

The term deterministic refers to the fact that on each input there is one and only one state to which the automaton can transition from its current state.

The inverse of Deterministic finite-state automata (DFA) is Nondeterministic finite-state automata (NFA) that may be in several states at once.

They are fast, without expensive backtracking.

Parsing Example

A Finite State Machine (FSM) will:

  • start with a default state (such as parsing)
  • then will parse a string character by character:
  • until it find a open token,
  • then, change your state
  • where you track and store all the characters
  • until you reach the closing token,
  • which then switches state back to the default one “parsing”.

A FSM versus a regular expression approach can come handy if you need to deal with matched nested parentheses or with deeper parsing level (different types of parentheses, etc.)

Definition

A DFA is denoted in the Five tuple notation as being a set of the following element.

<MATH> A = (Q, \sigma, \delta, q0, F) </MATH> where:

  • A is the name of the DFA
  • Q is its set of states
  • <math>\sigma</math> is its input symbols
  • <math>\delta</math> is its transition function
  • q its start state
  • F its set of accepting states

Finite

A finite automaton has the following function composition property

For the deterministic finite automata q, if the input string <math>s = y+z</math> , then processing a string s composed of two strings y and z is the same than processing first y then processing z.

<MATH>\delta(q,s) = \delta(\delta(q,y),z)</MATH>

where <math>\delta</math> is the state of an automaton q after processing a string (here s, y or z)

Documentation / Reference


Powered by ComboStrap