Here, I provide C++ implementation of a table-based Deterministic Finite Automaton. A DFA is a finite state machine that accepts/rejects finite strings of symbols and has a unique transition from each state on each input symbol.

A deterministic finite automaton *M* is a 5-tuple, (*Q*, Σ, δ, *q*_{0}, *F*), consisting of

- a finite set of states (
*Q*) - a finite set of input symbols called the alphabet (Σ)
- a transition function (δ :
*Q*× Σ →*Q*) - a start state (
*q*_{0}∈*Q*) - a set of final/accept states (
*F*⊆*Q*)

Let *w = a _{1}a_{2} … a_{n}* be a string over the alphabet Σ. The automaton

*M*accepts the string

*w*if a sequence of states,

*r*, exists in

_{0},r_{1}, …, r_{n}*Q*with the following conditions:

*r*=_{0}*q*_{0}*r*= δ(_{i+1}*r*,_{i}*a*), for_{i+1}*i*=*0, …, n−1**r*∈_{n}*F*.

The first condition says that the machine starts in the start state *q*_{0}. The second condition says that given each character of string *w*, the machine will transition from state to state according to the transition function δ. The last condition says that the machine accepts *w* if the last input of *w* causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton *rejects* the string. The set of strings *M* accepts is the language *recognized* by *M* and this language is denoted by *L(M)*.

Take a look at the C++ implementation. It requires a single pass over the input strings to decide whether or not they belong to the language of a given DFA.

Pingback: NFA simulation C++ implementation | Everything Under The Sun

Hey buddy thanks for showing a great example of DFA implementation. Your program has no errors but when I run it, dos windows does show up but soon it closes saying force close and in other compiler its just stuck on blank dos window.

It’s hard to speculate what’s happening on your machine without being able to reproduce it. Are you providing the DFA.txt file in the same folder as the code file?

And I was wondering, why did you use printf scanf if its a c++ implementation ?

We can still use scanf and printf in C++. I happen to like them. They give more control over parsing input and output.

Send me code that implement dfa by c++

The code given in this post is in c++. Link again here: https://github.com/kartikkukreja/blog-codes/blob/master/src/DFA%20simulation.cpp

Can you write a sample DFA text file ?

Here’s a sample DFA file (Link to DFA: http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/figures/dfa1.jpg):

4 2

3 0 1 3

0 1 1

0 2 2

1 1 1

1 2 3

2 1 2

2 2 2

3 1 1

3 2 2

Strings like (1 2 111 2) are accepted. Actions 1 and 2 correspond to a and b respectively in the diagram.

Thank you very much for your fast replies & yes now your program runs without error. I just couldnt figure out the format of input text file.

Hey man can you help me implementing this program in C language, I’m doing this from couple of hours but couldnt do it. I’ve this DFA implementation as a Assignement and have to submit it in like 6 hours.😦. you can email me for convo.

Here’s an implementation in C: https://github.com/kartikkukreja/blog-codes/blob/master/src/DFA%20simulation.c

algorithm implemanting dfa

The post has a link to the code in the last paragraph and repeated here: https://github.com/kartikkukreja/blog-codes/blob/master/src/DFA%20simulation.cpp

is this based off of the basic d-recognize algorithm??

I haven’t heard of this algorithm.