Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / Languages / C#

A Deterministic Finite Automaton Class in C#

2.70/5 (9 votes)
31 May 2007CPOL1 min read 1   1.5K  
A simple C# class implementation of a DFA for testing purposes

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 DFAs 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 (a.k.a. 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.

C#
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 a one-hour job...

History

  • 31st May, 2007: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)