deepdream of
          a sidewalk
Show Question
Math and science::Theory of Computation

Finite automata

A finite automaton (plural: automata) is a model of computation. Finite automata and their probabilistic counterpart Markov chains are useful tools when attempting to recognize patterns in data. Their formal definition has a 1-1 correspondence with a type of state diagram.

A finite automaton is a 5-tuple (Q,Σ,δ,q0,F), where:

  1. Q is a finite set called the states,
  2. Σ is a finite set called the alphabet,
  3. δ:Q×ΣQ is the transition function,
  4. q0Q is the start sate, and
  5. FQ is the set of accept states.

Processing of input

When an automaton receives an input string, it can either accept or reject it. A string is accepted if the automaton is in an accept state once the full input string is processed. Formally this is described as:

String acceptance

Let M=(Q,Σ,δ,q0,F) be a finite automaton and let w=w1w2...wn be a string where each wi is a member of the alphabet Σ. Then M accepts w iff a sequence of states r0,r1,...,rn is Q exists with three conditions:

  1. r0=q0
  2. ri+1=δ(ri,wi+1) for i=0,...,n1, and
  3. rnF

w is rejected iff it is not accepted.

If A is the set of all strings that machine M accepts, we say that A is the language of machine M and write L(M)=A. We say that M recognizes A.

State machine representation

A finite automaton has a 1-1 correspondence with a graphical state machine representation.



Source

Introduction to the Theory of Computation, Sipser
p35-36