Newest

Code of the Month

Code of the Day

All Time Hall of Fame

--------------------------------------------------------------------------------

Coding Contest

Ask A Pro Discussion Forum

Live Chat

Feedback

Customize My Info

--------------------------------------------------------------------------------

How To Link To Us

--------------------------------------------------------------------------------

Awards/Reviews/Raves!

Advertising/Media Kit

About the Site

World Home

Site Home

Other Sites

Search for a Job

Post a Job

Quick Search for:

C/ C++ Stats

Code: 190,912 lines

Jobs: 1,183 postings

Online Now: 4439 people

Latest Code Ticker for C/ C++ Run Dos programs within a dos program

By psalm on 6/21

Justified Print Function

By James Turk on 6/20

Split words in an Array

By psalm on 6/20

Resistor Calculator / Resistance Value Finder

By Jason Molenda on 6/19

(Screen Shot)

Sequential Renaming of Files

By Jason Molenda on 6/19

(Screen Shot)

Diceroller

By Mike Cramp on 6/19

DOS clock

By aakash deep mandhar on 6/19

Real Number Verification

By Mohammed Ali Akbani on 6/19

Implementing "and" and "or"

By psalm on 6/19

Click here to put this ticker on your site!

Add this ticker to your desktop!

Daily Code Email

To join the 'Code of the Day' Mailing List click here!

This Site on CD Over 7,000 submissions on a super fast CD!

Get Paid To Code Now taking pre-regis. on RentACoder!

Creating a Deterministic Finite Automaton (DFA) and executing it to recognize bit patterns

Submitted on: 2/28/2001 8:56:29 PM

By: Musawir Ali

Level: Intermediate

User Rating: Unrated

Compatibility:C++ (general), Microsoft Visual C++, Borland C++, UNIX C++

Users have accessed this code 585 times.

(About the author)

Demonstration of the working of a Deterministic Finite State Machine. The program is a linked list implementation of the machine. Easy to use application also provides the step by step transition of execution.

code:

Can't Copy and Paste this?

Click here for a copy-and-paste friendly version of this code!

Terms of Agreement:

By using this code, you agree to the following terms...

1) You may use this code in your own programs (and may compile it into a program and distribute it in compiled format for langauges that allow it) freely and with no charge.

2) You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.

3) You may link to this code from another website, but ONLY if it is not wrapped in a frame.

4) You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.

//**************************************

// Name: Creating a Deterministic Finite

// Automaton (DFA) and executing it to reco

// gnize bit patterns

// Description:Demonstration of the work

// ing of a Deterministic Finite State Mach

// ine. The program is a linked list implem

// entation of the machine. Easy to use app

// lication also provides the step by step

// transition of execution.

// By: Musawir Ali

// Inputs:machine states and links betwe

// en them. character string.

// Returns:a DFA model

// Assumes:Demonstration of the working

// of a Deterministic Finite State Machine.

// The program is a linked list implementat

// ion of the machine. Easy to use applicat

// ion also provides the step by step trans

// ition of execution.

//This code is copyrighted and has// limited warranties.Please see http://

// www.1CPlusPlusStreet.com/xq/ASP/txtCodeI

// d.1341/lngWId.3/qx/vb/scripts/ShowCode.h

// tm//for details.//**************************************

/*******************************************

* Name: Finite Automata *

* Author: Musawir Ali *

* Version: 1.0 *

* Note: creating a DFA *

*******************************************/

#include

using namespace std;

/******* Creating the node class for the DFA ******/

class node

{

public:

string name;

node *arc1;

node *arc2;

node *arc3;

node *next;

char final;

char start;

node(string n, char s, char f)

{

arc1=NULL;

arc2=NULL;

arc3=NULL;

next=NULL;

final = f;

start = s;

name = n;

}

};

/********* Building a node *********/

node *build_node(string name, char start, char final) //build a new node for the tree

{

node *new_node;

new_node = new node(name,start,final);

return(new_node);

}

/******** The DFA class ***********/

class dfa

{

public:

node *start;//pointer to the start state

void add(string na, char st, char fi, node *&r) //add state to the machine

{

if(r == NULL)

r = new node(na,st,fi);

else

{

add(na,st,fi,r->next);

}

void add(string nam, char sta, char fin) //overloaded function, passes start pointer

{

add(nam,sta,fin,start);

}

void print(node *s) //output the states and links of the DFA

{

if(s != NULL)

{

if(s->start=='y' && s->final=='y')

{

cout << s->name << " (start state & final state)" << endl;

if(s->arc1 != NULL)

cout << "a = " << s->arc1->name << "." << endl;

if(s->arc2 != NULL)

cout << "b = " << s->arc2->name << "." << endl;

if(s->arc3 != NULL)

cout << "c = " << s->arc3->name << "." << endl;

cout << endl;

}

else if(s->start=='y')

{

cout << s->name << " (start state)" << endl;

if(s->arc1 != NULL)

cout << "a = " << s->arc1->name << "." << endl;

if(s->arc2 != NULL)

cout << "b = " << s->arc2->name << "." << endl;

if(s->arc3 != NULL)

cout << "c = " << s->arc3->name << "." << endl;

cout << endl;

}

else if(s->final=='y')

{

cout << s->name << " (final state)" << endl;

if(s->arc1 != NULL)

cout << "a = " << s->arc1->name << "." << endl;

if(s->arc2 != NULL)

cout << "b = " << s->arc2->name << "." << endl;

if(s->arc3 != NULL)

cout << "c = " << s->arc3->name << "." << endl;

cout << endl;

}

else

{

cout << s->name << endl;

if(s->arc1 != NULL)

cout << "a = " << s->arc1->name << "." << endl;

if(s->arc2 != NULL)

cout << "b = " << s->arc2->name << "." << endl;

if(s->arc3 != NULL)

cout << "c = " << s->arc3->name << "." << endl;

cout << endl;

}

print(s->next);

}

void print()

{

print(start);

}

dfa() //Default constructor

{

start = NULL;

}

link(string nam1, string nam2, char le, node *&st) //check and link states with in a DFA

{

if(st != NULL)

{

if(st->name != nam1)

link(nam1,nam2,le,st->next);

else

{

node *temp_ptr;

temp_ptr = start;

while(temp_ptr != NULL)

{

if(temp_ptr->name == nam2)

{

if(le == 'a')

{

if(st->arc1 == NULL)

st->arc1 = temp_ptr;

else

cout << "This link is already occupied!" << endl;

}

else if(le == 'b')

{

if(st->arc2 == NULL)

st->arc2 = temp_ptr;

else

cout << "This link is already occupied!" << endl;

}

else if(le == 'c')

{

if(st->arc3 == NULL)

st->arc3 = temp_ptr;

else

cout << "This link is already occupied!" << endl;

}

temp_ptr = NULL;

}

else if(temp_ptr->next != NULL)

temp_ptr = temp_ptr->next;

else

{

cout << "The state " << nam2 << " was not found!" << endl;

temp_ptr = temp_ptr->next;

}

else

cout << "Node " << nam1 << " not found!" << endl;

}

link(string nam1, string nam2, char let)

{

link(nam1,nam2,let,start);

}

};

/************* The Main function **************/

void main()

{

cout << "******************************************" << endl;

cout << "* Linked List DFA Implementation *" << endl;

cout << "******************************************" << endl;

cout << endl;

cout << "Steps:" << endl;

cout << " 1) Enter number of states" << endl;

cout << " 2) Enter name of each state and say if it is a final state" << endl;

cout << " 3) Establish links between states" << endl;

cout << " 4) Pass a string to execute" << endl;

cout << "\n" << endl;

dfa mydfa;

string name;

int num_states;

char start='n';

char final;

cout << "Enter number of states: ";

cin >> num_states;

for(int i=0; i < num_states; i++) //create states and add them to the DFA

{

if(i==0)

{

start = 'y';

cout << "Enter the name of start state q" << i << ": ";

cin >> name;

cout << "Is this a final state? : ";

cin >> final;

if(final=='y' || final == 'Y')

final = 'y';

else if(final=='n' || final == 'N')

final = 'n';

else

final = 'n';

mydfa.add(name,start,final);

start = 'n';

}

else

{

cout << "Enter the name of state q" << i << ": ";

cin >> name;

cout << "Is this a final state? : ";

cin >> final;

if(final=='y' || final == 'Y')

final = 'y';

else if(final=='n' || final == 'N')

final = 'n';

else

final = 'n';

mydfa.add(name,start,final);

}

/***** Output the states entered *********/

cout << "\n\nYou entered the states: " << endl;

mydfa.print();

cout << "\n" << endl;

string name1;

string name2;

char letter;

char choice = 'n';

cout << "Create links between states? : ";

cin >> choice;

cout << endl;

/********** Start creating transition links between states **********/

while(choice == 'y' || choice =='Y')

{

cout << "Enter state's name to be linked from: ";

cin >> name1;

cout << "Enter state's name to be linked to: ";

cin >> name2;

cout << "Enter link name : ";

cin >> letter;

mydfa.link(name1,name2,letter);

cout << endl;

cout << "Create links between states? : ";

cin >> choice;

cout << endl;

}

cout << "The states are linked as below: \n" << endl;

mydfa.print();

string run;

cout << "\nEnter a string to run on the machine: ";

cin >> run;

node *temp_ptr;

node *reject;

reject = build_node("reject",'n','n');

temp_ptr = mydfa.start;

char go;

/******* run (execute) the string on the machine *********/

for(i=0;i

{

go = run[i];

if(temp_ptr->arc1 == NULL && temp_ptr->arc2 == NULL && temp_ptr->arc3 == NULL)

{

cout << "No path found from state " << temp_ptr->name << "!, going to reject state." << endl;

temp_ptr = reject;

}

else if(go == 'a' && temp_ptr->arc1 != NULL)

{

cout << "Reading an 'a' and moving to state " << temp_ptr->arc1->name << "." << endl;

temp_ptr = temp_ptr->arc1;

}

else if(go == 'b' && temp_ptr->arc2 != NULL)

{

cout << "Reading a 'b' and moving to state " << temp_ptr->arc2->name << "." << endl;

temp_ptr = temp_ptr->arc2;

}

else if(go == 'c' && temp_ptr->arc3 != NULL)

{

cout << "Reading a 'c' and moving to state " << temp_ptr->arc3->name << "." << endl;

temp_ptr = temp_ptr->arc3;

}

else

{

cout << "Reading " << go << " and moving to reject state. Path not found." << endl;

temp_ptr = reject;

}

/******* String accepted or not? *********/

if(temp_ptr->final=='y')

cout << "\nThis string is accepted!" << endl;

else

cout << "\nThis string is not accepted!" << endl;

char trya;

/*********** try another string **********/

cout << "\n\nTry another string? : ";

cin >> trya;

while(trya == 'y' || trya == 'Y')

{

cout << "\nEnter a string to run on the machine: ";

cin >> run;

temp_ptr = mydfa.start;

for(i=0;i

{

go = run[i];

if(temp_ptr->arc1 == NULL && temp_ptr->arc2 == NULL && temp_ptr->arc3 == NULL)

{

cout << "No path found from state " << temp_ptr->name << "!, going to reject state." << endl;

temp_ptr = reject;

}

else if(go == 'a' && temp_ptr->arc1 != NULL)

{

cout << "Reading an 'a' and moving to state " << temp_ptr->arc1->name << "." << endl;

temp_ptr = temp_ptr->arc1;

}

else if(go == 'b' && temp_ptr->arc2 != NULL)

{

cout << "Reading a 'b' and moving to state " << temp_ptr->arc2->name << "." << endl;

temp_ptr = temp_ptr->arc2;

}

else if(go == 'c' && temp_ptr->arc3 != NULL)

{

cout << "Reading a 'c' and moving to state " << temp_ptr->arc3->name << "." << endl;

temp_ptr = temp_ptr->arc3;

}

else

{

cout << "Reading " << go << " and moving to reject state. Path not found." << endl;

temp_ptr = reject;

}

if(temp_ptr->final=='y')

cout << "\nThis string is accepted!" << endl;

else

cout << "\nThis string is not accepted!" << endl;

cout << "\n\nTry another string? : ";

cin >> trya;

}

cout << "\n\nEnd of demonstration" << endl;

}