2 - Finite state automata

• Transition table

  
• State diagram

  
• A parity checking machine : proces bitstring from left to right

  needed :

  • intital state q0
  • final state q1

  accepted if it ends in q1, rejected otherwise
• parity

  if an integer number is odd or even
• runtime


  number of steps it requires to compute
• runtime parity

  log_2 (n) + 1
• Determinstic finite automate

  finite state machines
• DFA : accept/reject strings by sequentially processing symbols :

  1. a finite and nonempty set of internal states Q
  2. the alphabet
  3. a transition function that describes the inner working
  4. a desgined start state
  5. a subset of accept states

  5-tuple M = (Q, alphabet, delta, q0, F)
• State diagram rules :

  1. States are denoted by circles
  2. circles connected by directed arrows + alphabet symbols label them
  3. transition function is characterized by the arrows + labels
  4. start state is the circle with the arrow out of nowhere
  5. accept states are double circles
• DFA computations

  A) string

  B) accepts

  C) exists

  D) q0

  E) rn

  F) accepts

  G) rejects

  
• DFA state has exactly one exiting transtion arrow for each symbol of the alphabet + arrows can only be labeled by symbols from the alphabet.

  --> improves predicatability --> deterministic
• NFA breaks the rules in two ways :

  • for each circle there can be zero/one/more than one exting arrow
  • the arrow labeled empty
• NFA accepts a state if the probaility of ending up in a accept state is strictly larger then zero. Nondeterminism is really a statement about possibilities (not probabilities)
• equivalence between NFAs and DFAs

  all computations performed by a NFA an be perfectly reproduced by a DFA, however, there may be an enxponential overhead in number of states required
• It can be very expensive to build a DFA taht does the same job as NFA
• NFA

  Non-deterministic finite automaton