DFA simulation C++ implementation

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, Σ, δ, q0F), 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 (q0 ∈ Q)
  • a set of final/accept states (F ⊆ Q)

Let w = a1a2 … an be a string over the alphabet Σ. The automaton M accepts the string w if a sequence of states, r0,r1, …, rn, exists in Q with the following conditions:

  1. r0 = q0
  2. ri+1 = δ(riai+1), for i = 0, …, n−1
  3. rn ∈ F.

The first condition says that the machine starts in the start state q0. 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.

16 thoughts on “DFA simulation C++ implementation

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

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

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s