www.delorie.com/gnu/docs/gnugo/gnugo_162.html search
GNU Go Documentation

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 13.0.2 What is a DFA

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 Knuth-Morris-Pratt or Boyer-Moore algorithms are based on DFA's (See http://www-igm.univ-mlv.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:

 `````` /* dfa state */ typedef struct state { int next[4]; /* transitions for EMPTY, BLACK, WHITE and OUT_BOARD */ attrib_t *att; } state_t; /* dfa */ typedef struct dfa { attrib_t *indexes; /* Array of pattern indexes */ int maxIndexes; state_t *states; /* Array of states */ int maxStates; } dfa_t;``` ```

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

 webmaster delorie software   privacy Copyright © 2003   by The Free Software Foundation Updated Jun 2003