CSC416 lecture note on Fintite State Automata 

[J: 10.1,2,4] Automata, Grammars and Languages (1)

0. Intro to Finite State Automata

• A finite state automaton (FSA) is an abstract model of a computing machine with a primitive memory.
• An FSA can only model rather easy computations. But it is very useful: there are many things/machines in our every-day life that perform this kind of computations. This means our world is not so complex (?!)
• An FSA is basically a directed graph with labeled edges, and each vertex represents a state in the computation. Then the computation is performed by making transitions between states according to the input.
• Example (1): A 30 cent newspaper vending machine

  

• Example (2): used for pattern matching

1. Finite State Machine

• The machine which is the core of an FSA.
• As the computation makes state transitions, the machine produces some output.
• Definition: A finite state machine M = (I, O, S, f, g, s), where
  • I -- set of possible input symbols
  • O --set of possible output symbols
  • S --set of states
  • f --a next-state function from S * I into S
  • g --an output function from S * I into O
  • s -- the initial state (s Î S)
• Input & Output for an FSM
  • Input -- a string consisting of symbols in I
  • Output -- a string consisting of symbols in O
• Example (10.1.5, 10.5.6):
  • A machine M = (I, O, S, f, g, s), where
    • I = {a,b}
    • O = {0,1}
    • S = {s₀, s₁}
    • s = s₀
    • f, g -- given by a transition diagram or a transition table

      

      f(s0, a) = s0	g(s0, a) = 0
      f(s0, b) = s1	g(s0, b) = 1
      f(s1, a) = s1	g(s1, a) = 1
      f(s1, b) = s1	g(s1, b) = 0

  • Sample Input/Output:
    • Input = aababba; Output = 0011001
    • Input = aaa; Output = 000
• Examples:
  1. Exercise #21 (p. 457): 
     An FSM which outputs 1 if an even number of 1's have been input; otherwise outputs 0.  The input is always a bit string (i.e., 0 or 1).

     
     
     
     
     
     
     
     
     
     
     

  2. Exercise #24 (p. 457): 
     An FSM which outputs 1 whenever it sees 101; otherwise outputs 0.  The input is always a bit string (i.e., 0 or 1).
     
     

2. Finite State Automata

• A finite state automaton is a special kind of FSM, where
  • Output symbols are {0, 1}.
  • States to which a transition with output 1 exists are called accepting states (usually marked with double circles).
  • For the reason above, output symbols in transition diagram/table are often omitted.
• Any input to an FSA which lands in one of the accepting states at the end of transitions is accepted by the machine. Thus, the FSA is used to recognize input strings.
• Definition: A finite state automaton A = (I, S, f, A, s), where
  • I -- set of possible input symbols
  • S --set of states
  • f --a next-state function from S x I into S
  • A -- set of accepting states (A Í S)
  • s -- the initial state (s Î S)
• A null string is accepted only if the start state is also an accepting state.
• IMPORTANT NOTE:  
  • For each state, transitions for ALL input symbols must be well-defined.

• Example (10.2.2):
  • I = {a, b}
  • S = {s₀, s₁, s₂}
  • A = {s₁, s₂}
  • s = s₀
  • f = given by the following transition diagram

    

  Input string	Accept/Reject?
  abbaa
  bbabb
  ababaaa

• Equivalency of two FSA's

  Let A and A' be FSA. A is equivalent to A' if the strings accepted by A is the same as the strings accepted by A', that is, Ac(A) = Ac(A').

• More Examples of (deterministic) FSA's
  1. Accept strings that contain an odd number of a's.
     • I = {a,b}
     • Transition diagram:

       
       
       

       
       
       
       

  2. Accept strings that contain exactly one a
     • I = {a,b}
     • Transition diagram:
       
       
       

       
       
       

       
       

  3. Accept strings of the form a*b*c*
     • I = {a,b,c}
     • Transition diagram:
       
       
       
       
       
       
       
       
       
       
       
       

3. Nondeterministic Finite State Automata (NDFSA's)

• A nondeterministic finite state automata (NDFSA) is a special kind of FSA (or deterministic FSA -- DFSA), where
  • next-state function f is not defined for all S * I (i.e., some missing transitions); and/or
  • next-state function f has multiple transitions for a given [state, symbol] pair (f: S * I -> P(S), a powerset of S)
  • Example (10.4.6):

    

• Strings accepted by NDFSA's
  • A string is accepted by a nondeterministic finite state automata A = (I, S, f, A, s) if there is any path (i.e., at least one path )from the start state to an accepting state. Let a = [x₁,..,x_n] be a nonnull string. a is accepted by A if there exists a sequence of states [s₀,..,s_n] such that
    • s₀ = s
    • s_i Î f(s_i-1, x_i) for all i, 1 <= i <= n
    • s_n Î A
  • A null string is accepted only if s₀ Î A.
• IMPORTANT NOTES:
  • A string is accepted only if ALL input symbols are processed AND the last state is one of the accepting states at the same time.  
  • So, a string is rejected if 
    • the processing gets stuck because there is no transition specified for the current input symbol, no matter what state (accepting/non-accepting) the processing stops at; or
    • the processing succeeded till the end of an input string, and the last state is a  non-accepting state.

• More Examples of non-deterministic FSA's
  1. Accept strings that start with ab
     • I = {a,b}
     • Transition diagram:

       
       
       

       
       
       
       

  2. Accept strings that contain ab
     • I = {a,b}
     • Transition diagram:
       
       
       
       
       
       
       

       
       

  3. (Section 10.4, Exercise #27)
     Accept strings that start with ab but do not end with ab.
     • I = {a,b}
     • Transition diagram: