CS 3723
 Programming Languages 
  Computer Simulations  
  of Finite Automata  

Introduction: This page goes along with the page Subset Algorithm, giving computer simulations of the examples there.

Example 1:

NFA for (a|b)*abb
 

DFA for (a|b)*abb

Subset Algorithm (Tables)
NFA, (a|b)*abb
Stateab
  0 (start)0,10
  1−2
  2−3
  3 (term)−−
 
DFA, (a|b)*abb
Statesab
  {0} (start) {0,1}{0}
  {0,1} {0,1}{0,2}
  {0,2} {0,1}{0,3}
  {0,3} (term) {0,1}{0}

Computer Simulations of Automata Above
NFA Simulation DFA Simulation Same DFA, treated as NFA
NFA:
s  0 --> [a, 1] --> [b, 0] --> [a, 0]
   1 --> [b, 2]
   2 --> [b, 3]
t  3 --> 

execNFA: execStr: ababbab$
 | 0 1 2 3 
 | - - - - 
 : 1 0 0 0  s
a: 1 1 0 0  s
b: 1 0 1 0  s
a: 1 1 0 0  s
b: 1 0 1 0  s
b: 1 0 0 1  st
a: 1 1 0 0  s
b: 1 0 1 0  s

DFA:
s  0 --> [b, 0] --> [a, 1]
   1 --> [b, 2] --> [a, 1]
   2 --> [b, 3] --> [a, 1]
t  3 --> [b, 0] --> [a, 1]

execDFA: execStr: ababbab$



s 0 --a--> 1
  1 --b--> 2
  2 --a--> 1
  1 --b--> 2
  2 --b--> 3 t
  3 --a--> 1
  1 --b--> 2

DFA:
s  0 --> [b, 0] --> [a, 1]
   1 --> [b, 2] --> [a, 1]
   2 --> [b, 3] --> [a, 1]
t  3 --> [b, 0] --> [a, 1]

execNFA: execStr: ababbab$
 | 0 1 2 3 
 | - - - - 
 : 1 0 0 0  s
a: 0 1 0 0  
b: 0 0 1 0  
a: 0 1 0 0  
b: 0 0 1 0  
b: 0 0 0 1  t
a: 0 1 0 0  
b: 0 0 1 0

Example 2:

NFA for (a|b)*(aa|bb)(a|b)*
 

DFA for (a|b)*(aa|bb)(a|b)*

Subset Algorithm (Tables)
NFA, (a|b)*(aa|bb)(a|b)*
Stateab
  0 (start)0,10,2
  13−
  2−3
  3 (term)33
 
DFA, (a|b)*(aa|bb)(a|b)*
Statesab
  {0} (start) {0,1}{0,2}
  {0,1} {0,1,3}{0,2}
  {0,2} {0,1}{0,2,3}
  {0,1,3} (term) {0,1,3}{0,2,3}
  {0,2,3} (term) {0,1,3}{0,2,3}

Computer Simulation of NFA Above Left
NFA:
s  0 --> [b, 2] --> [a, 1] --> [b, 0] --> [a, 0]
   1 --> [a, 3]
   2 --> [b, 3]
t  3 --> [b, 3] --> [a, 3]

execNFA: execStr: ababbaaba$
 | 0 1 2 3 
 | - - - - 
 : 1 0 0 0  s
a: 1 1 0 0  s
b: 1 0 1 0  s
a: 1 1 0 0  s
b: 1 0 1 0  s
b: 1 0 1 1  st
a: 1 1 0 1  st
a: 1 1 0 1  st
b: 1 0 1 1  st
a: 1 1 0 1  st

State Minimization:

Minimal DFA for (a|b)*(aa|bb)(a|b)*
With States Renamed
  
Computer Simulation of DFA At Left
DFA:
s  0 --> [b, 2] --> [a, 1]
   1 --> [b, 2] --> [a, 3]
   2 --> [b, 3] --> [a, 1]
t  3 --> [b, 3] --> [a, 3]

execDFA: execStr: ababbaaba$, states: 4
s 0 --a--> 1
  1 --b--> 2
  2 --a--> 1
  1 --b--> 2
  2 --b--> 3 t
  3 --a--> 3 t
  3 --a--> 3 t
  3 --b--> 3 t
  3 --a--> 3 t

Example 3: No simulation of this example so far.

Example 4:

NFA for (a|b)*a(a|b)(a|b)
DFA for (a|b)*a(a|b)(a|b)
Computer Simulation of NFA Above
NFA:
s  0 --> [a, 1] --> [b, 0] --> [a, 0]
   1 --> [b, 2] --> [a, 2]
   2 --> [b, 3] --> [a, 3]
t  3 --> 

execNFA: execStr: aaababbb$, states: 4
 | 0 1 2 3 
 | - - - - 
 : 1 0 0 0  s
a: 1 1 0 0  s
a: 1 1 1 0  s
a: 1 1 1 1  st
b: 1 0 1 1  st
a: 1 1 0 1  st
b: 1 0 1 0  s
b: 1 0 0 1  st
b: 1 0 0 0  s

Next, start with a similar NFA with 1 additional state. In this case the DFA has twice as many states, and it again is minimal.


NFA for (a|b)*a(a|b)(a|b)(a|b)
DFA for (a|b)*a(a|b)(a|b)(a|b)
Note: Label on arrow from (03) to ((04)) should be "b".
Computer Simulation of NFA Above
NFA:
s  0 --> [a, 1] --> [b, 0] --> [a, 0]
   1 --> [b, 2] --> [a, 2]
   2 --> [b, 3] --> [a, 3]
   3 --> [b, 4] --> [a, 4]
t  4 --> 

execNFA: execStr: aaaabaabbababbab$
 | 0 1 2 3 4 
 | - - - - - 
 : 1 0 0 0 0  s
a: 1 1 0 0 0  s
a: 1 1 1 0 0  s
a: 1 1 1 1 0  s
a: 1 1 1 1 1  st
b: 1 0 1 1 1  st
a: 1 1 0 1 1  st
a: 1 1 1 0 1  st
b: 1 0 1 1 0  s
b: 1 0 0 1 1  st
a: 1 1 0 0 1  st
b: 1 0 1 0 0  s
a: 1 1 0 1 0  s
b: 1 0 1 0 1  st
b: 1 0 0 1 0  s
b: 1 0 0 0 1  st
b: 1 0 0 0 0  s

NFAs with ε moves:

NFA for a*b*c*

DFA for a*b*c*

Computer Simulation of NFA Above Computer Simulation of DFA Above
NFA:
s  0 --> [@, 1] --> [a, 0]
   1 --> [@, 2] --> [b, 1]
t  2 --> [c, 2]

execNFA: execStr: aabbbccab$, states: 3
 | 0 1 2 
 | - - - 
 : 1 1 1  st
a: 1 1 1  st
a: 1 1 1  st
b: 0 1 1  t
b: 0 1 1  t
b: 0 1 1  t
c: 0 0 1  t
c: 0 0 1  t
a: 0 0 0  
b: 0 0 0  

DFA:
ts 0 --> [c, 2] --> [b, 1] --> [a, 0]
t  1 --> [c, 2] --> [b, 1] --> [a, 3]
t  2 --> [c, 2] --> [b, 3] --> [a, 3]
   3 --> [c, 2] --> [b, 3] --> [a, 3]



execDFA: execStr: aabbbccab$, states: 4
s 0 --a--> 0 t
s 0 --a--> 0 t
s 0 --b--> 1 t
  1 --b--> 1 t
  1 --b--> 1 t
  1 --c--> 2 t
  2 --c--> 2 t
  2 --a--> 3
  3 --b--> 3

Computer Simulation of DFA for (a|b)abb:

DFA for (a|b)abb

DFA Sim of DFA Above Same DFA, treated as NFA
DFA:
s  0 --> [b, 0] --> [a, 1]
   1 --> [b, 2] --> [a, 1]
   2 --> [b, 3] --> [a, 1]
t  3 --> [b, 0] --> [a, 1]

execDFA: execStr: ababbab$



s 0 --a--> 1
  1 --b--> 2
  2 --a--> 1
  1 --b--> 2
  2 --b--> 3 t
  3 --a--> 1
  1 --b--> 2

DFA:
s  0 --> [b, 0] --> [a, 1]
   1 --> [b, 2] --> [a, 1]
   2 --> [b, 3] --> [a, 1]
t  3 --> [b, 0] --> [a, 1]

execNFA: execStr: ababbab$
 | 0 1 2 3 
 | - - - - 
 : 1 0 0 0  s
a: 0 1 0 0  
b: 0 0 1 0  
a: 0 1 0 0  
b: 0 0 1 0  
b: 0 0 0 1  t
a: 0 1 0 0  
b: 0 0 1 0

Revision date: 2013-09-21. (Please use ISO 8601, the International Standard.)