Designing DFA

CERTIFICATE

This is to certify that Mr. Varun Arora, Mr. Ujjwal Saini and Mr. Vivek Sharma of B.Tech. in Computer Science Engineering have carried out the work presented in the project of entitled “Designing DFA using C++” as a part of Third year programme of Bachelor of Technology in Computer Science from Amity School of Engineering and Technology, Amity University, Noida, Uttar Pradesh under my supervision.

Acknowledgements

We would like to thank the people who helped us in completing this project. We express our Gratitude to Mr. Ramen Ghosh to give us a chance to work on such an interesting topic, which helped us a lot in increasing our knowledge as well as our scope so we thank you sir for letting us to choose this project.

We owe a lot of credit to our parents and friends who supported us in our project landing to the completion of the project. We would also like to thank our elders for giving us important information for our project. And thanks to all others for extending the fullest cooperation during the preparation of the project and assisting us in their every possible way for its successful completion. We also confirm that the project submitted by us is totally authentic and the research undertaken was not copied from external sources.

Abstract

This project relates to design a DFA (Deterministic Finite Automata) with the given inputs using graphics in C programming language. In the theory of computation, a deterministic finite state machine is a finite state machine where for each pair of state and input symbol there may be several possible next states. The machine starts in the specified initial state and reads in a string of symbols from its alphabet. The automaton uses the state transition function T to determine the next state using the current state, and the symbol just read or the empty string. However, "the next state of an DFA depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in". If, when the automaton has finished reading, it is in an accepting state, the DFA is said to accept the string, otherwise it is said to reject the string.

Requirement Analysis and Specification

To design a program or software that will be a FA( Finite Automata ) tool that will handle different types of Automata like NFA( non deterministic finite Automata ), DFA( deterministic finite automata ) etc.

Expected solution:-

The problem to design the above mentioned tool is programming language independent and hence can be made on different platforms but if the selection is to be made out of programming language, the available choices to design a DFA and check the acceptance of any string to that DFA are:-

1. Java:-JFLAP is a software with formal language topics including NFA, non deterministic push down automata, TM, and several types of grammars. It also allows one to convert NFA to DFA which can be modified further.
2. C/C++:-In C/C++, graphics libraries can be used to draw NFA or DFA depending upon the transition table which contains transitions between the states and initial and final state which is to be input before the designing of DFA and then the program will also ask for a string of input alphabets which will be checked for the acceptance to that DFA.

Opted solution:-

As in Java, the JFLAP tool already designed, there is no such programming software in C which draws DFA or check the acceptance of string. The opted solution is designing of DFA using C/C++ and graphics library present with C/C++ programming language.

Software Requirement:-

Windows: xp, 2000 or 98. Turbo c or broadband C++ with graphics library. For vista or windows 7, virtual pc is required.

Input Table Format

D	A	B
q1	q4	q2
q2	q3	q7
q3	q1	q4
q4	q8	q2
q5	q7	q6
q6	q1	q8
q7	q1	-
q8	q3	q7

Algorithm

1. Step 1. Declare Structure node {

int num;

int xc, yc;

int ina;

int inb;

}

Step 2. Initialise graphics

Step 3. Display Welcome Screen

Step 4. Input number of states

Step 5. If number of states greater than 8, go to step 4.

Step 6. Initialise center of states according to number of states.

Step 7. Call table (states). Algorithm 2.

Step 8. Call state input (). Algorithm 3

Step 9. Call draw (). Algorithm 4

Step 10. Call Check (). Algorithm 5

Step 11. Exit.

2. Table (states)

Step 1. Put values of transitions if no transition then put ‘-‘

Step 2. Draw table according to number of states as

D	A	B
Q1	-	-
Q2	-	-
Q3	-	-

3. State input ()

Step 1. Input Transition

Step 2. For state from i=1 to number of states

Repeat steps 3 to 7

Step 3. Input transition of states q: for input a

Step 4. If qi – a – is greater than number of states go to step 3.

Step 5. Input transition of states q: for input b

Step 6. If qi – b– is greater than number of states go to step 5.

Step 7. Draw table call table () Algorithm 2.

Step 8. Input initial state is

Step 9. If is greater than number of states go to step 8.

Step 10.Input Final state fs

Step 11. If fs greater than number of states, go to step 10.

Step 12. Display ‘>‘ for initial state and ‘ * ‘ for final state.

4. Draw ()

Step 1. For states from i = 1 to number of states

Repeat step 2

Step 2. If transition of state qi = qi , put a (*) inside the state(circle) else

Draw states qi for input a and b

Step 3. Draw double circle for final state and arrow for initial state.

5. Check ()

Step 1. Ask user if he/she want to check the acceptance of string to that DFA

If yes

Go to step 2

Else

Go to step 5

Step 2. Input the string

Step 3. Check whether it contains alphabets other than ‘a’ and ‘b’

If yes

Show error and go to step 1 else go to step 4

Step 4. Displays the transition of states for that string and call table () Algorithm 2.

Step 5. Displays thank you page.

Implementation and Software Requirement

This project can be used to obtain a DFA by giving the transition of various different states on a particular input alphabet. This program can also check the acceptance of a string (That is the machine is in accepting state after the acceptance of string, or not).

The set of all strings accepted by an DFA is the language the DFA accepts. This language is a regular language.This project is designed using the concepts of C/C++ languages using turbo C++ compiler and graphics in C++.The project is based on Theory of automata. The deterministic Finite Automata is designed through taking input as set of states and the transition from one state to another by giving an input. The project is made using Turbo c++ and the language used for making this project is the language C. In this the graphics library of C is also used to design the automata machine. And this program will also check the acceptance of the given string by transiting from one state to another, if the automata stop at accepting state then the string is accepted, else it will show an error.

Conclusion

In this project the concept of c++ and graphics is used. In this first the user is ask to enter the number of states (max 8). Then the transition table appears. Then it asks the user to enter the values for transition of various states that is for “a” and “b” respectively. Then on entering the values for transition of various states the table will appear indicating the states to which transition has to take place. It will keep on asking to enter the values till the maximum number of states is reached.

After this it asks to enter the initial state and final state. Now the table is complete with the initial state indicated by “>” and the final state by “*”. Now press enter to get the equivalent DFA. Here the red color line indicates the transition for value “a” and Green color line indicates the transition for value “b”.

“*” indicates self state.

Achievement

This project deals with the designing of DFA using c++ and graphics. The program uses graphics functions, 

which we have learnt in c++. 

In this project concepts of Theory of automata and Computer Graphics have been used which were taught

 in the early semesters.

As this project is based on TAC, the concept of DFA is successfully implemented and also to check the acceptance 

of any string to that DFA being designed by the program is taken from TAC. To draw the states and showing the transition of states in Transition Diagram, some concepts of Computer Graphics have been used like Bresenham's Algorithm to draw the states shown by circles, Rotation algorithm to join the states according to transition table. Basic graphics concepts such as rectangle, line colors etc. have also been used.