12,554,623 members (57,575 online)
Article
alternative version

29.8K views
21 bookmarked
Posted

# A Deterministic Finite Automaton Class in C#

, 31 May 2007 CPOL
 Rate this:
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`.

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

## Share

 Germany
No Biography provided

## You may also be interested in...

 Pro Pro