www.delorie.com/gnu/docs/gnugo/gnugo_162.html  search 
Buy GNU books!  
[ < ]  [ > ]  [ << ]  [ Up ]  [ >> ]  [Top]  [Contents]  [Index]  [ ? ] 
The acronym DFA means Deterministic Finite state Automaton (See http://www.eti.pg.gda.pl/~jandac/thesis/node12.html or Hopcroft & Ullman "Introduction to Language Theory" for more details). DFA are common tools in compilers design (Read Aho, Ravi Sethi, Ullman "COMPILERS: Principles, Techniques and Tools" for a complete introduction), a lot of powerfull text searching algorithm like KnuthMorrisPratt or BoyerMoore algorithms are based on DFA's (See http://wwwigm.univmlv.fr/~lecroq/string/ for a bibliography of pattern matching algorithms).
Basically, a DFA is a set of states connected by labeled transitions. The labels are the values read on the board, in gnugo these values are EMPTY, WHITE, BLACK or OUT_BOARD, denoted respectively by '.','O','X' and '#'.
The best way to represent a dfa is to draw its transition graph: the pattern "????..X" is recognized by the following DFA:
.,X,O .,X,O .,X,O .,X,O . . X [1]>[2]>[3]>[4]>[5]>[6]>[7]>[8 OK!] Start 
This means that starting from state [1], if you read '.','X' or 'O' on the board, go to state [2] and so on until you reach state [5]. From state [5], if you read '.', go to state [6] otherwise go to error state [0]. And so on until you reach state [8]. As soon as you reach state [8], you recognize Pattern "????..X"
Adding a pattern like "XXo" ('o' is a wildcard for not 'X') will transform directly the automaton by synchronization product (13.0.4 Building the DFA). Consider the following DFA:
Start .,O .,X,O .,O,X .,X,O . . X [1]>[2]>[3]>[4]>[5]>[6]>[7]>[8 OK!]  ^ ^ ^  .,O          X      .,X,O       X  X  O,.  >[9]>[A]>[B OK!] 
By adding a special error state and completing each state by a transition to error state when there is none, we transform easily a DFA in a Complete Deterministic Finite state Automaton (CDFA). The synchronization product (13.0.4 Building the DFA) is only possible on CDFA's.
Start .,O .,X,O .,O,X .,X,O . . X [1]>[2]>[3]>[4]>[5]>[6]>[7]>[8 OK!]  ^ ^ ^     .,O                X   X,O  .,O X,.,O    .,X,O             X  X  O,.  \ / \ / \ / >[9]>[A]>[B OK!] [0 Error state !] 
The graph of a CDFA is coded by an array of states: The 0 state is the "error" state and the start state is 1.
 state  .  O  X  #  att  1  2  2  9  0  2  3  3  3  0  3  4  4  4  0  5  6  0  0  0  6  7  0  0  0  7  0  0  8  0  8  0  0  0  0  Found pattern "????..X" 9  3  3  A  0  A  B  B  4  0  B  5  5  5  0  Found pattern "XXo"  
To each state we associate an often empty list of attributes which is the list of pattern indexes recognized when this state is reached. In '`dfa.h'' this is basically represented by two stuctures:

[ < ]  [ > ]  [ << ]  [ Up ]  [ >> ]  [Top]  [Contents]  [Index]  [ ? ] 
webmaster  delorie software privacy 
Copyright © 2003 by The Free Software Foundation  Updated Jun 2003 