Click here to Skip to main content
12,552,255 members (48,258 online)
Click here to Skip to main content
Add your own
alternative version


21 bookmarked

A Deterministic Finite Automaton Class in C#

, 31 May 2007 CPOL
Rate this:
Please Sign up or sign in to vote.
A simple C# class implementation of a DFA for testing purposes


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.


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.

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...


  • 31st May, 2007: Initial post


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


About the Author

Germany Germany
No Biography provided

You may also be interested in...


Comments and Discussions

-- There are no messages in this forum --
| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.161021.1 | Last Updated 31 May 2007
Article Copyright 2007 by hanzzoid
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid