A Deterministic Finite Automaton Class in C#

• Download DFA.zip - 1.3 KB

Introduction

The above downloadable zip file contains just a small C# class, which is a simple implementation of a deterministic finite automaton (DFA). I encountered the matter during the theoretical computer science course at my college, and found it useful to be able to actually test all those DFA's we had to construct merely on paper.

Background

For those who don't know, a DFA is a theoretical machine model behind the concept of regular languages; and a DFA in particular is equivalent to a regular expression. For a complete introduction, see this wiki article.

Using the code

Just add the class to an existing project.

A simple example DFA for the regular language PARITY, which is the language of all binary strings with an odd number of ones, goes like this: f is the set of accepting states, delta is the transition matrix (aka state transition table, see comments within the code for more explanations about the structure of this matrix), and M our thereby defined DFA. In the for-loop, a little statistic testing is performed: the DFA-class contains a static RandomString method which is used here to generate a binary string of length 10.

Then, assuming you have a method called ArrayToString at your disposal (which should return a string), the random string is outputted, followed by the information whether the DFA M accepts this string.

 int[] f = new int[] { 1 };
 int[,] delta = new int[,] { { 0, 1 }, { 1, 0 } };

 DFA M = new DFA(delta, f);
 int[] s;

 for (int i = 0; i < 10; i++)
 {
     s = DFA.RandomString(10, 2);
    textBox1.AppendText(ArrayToString(s) + " - " 
    + M.Accepts(s).ToString() + System.Environment.Newline);
 } 

Points of Interest

The next step to perform could be a routine for the graphical display of such automata, but that seems to be more than an one-hour job...

Yours,

hanzzoid.