Piyush Kumar

Technical Report Writing on
Deterministic Finite Automata

Submitted by
Name: Piyush Kumar
Department: Computer Science and Engineering
Semester: 4th
Roll Number:16900122038
Department of : Computer Science and Engineering

ACADEMY of TECHNOLOGY
AEDCONAGAR, HOOGHLY-712121 WEST
BENGAL, INDIA
1 . Abstract
This technical report explores the theoretical foundations, design principles, and practical
applications of Deterministic Finite Automata (DFA). Beginning with an overview of basic
concepts, the report progresses to delve into DFA construction, optimization techniques,
and real-world implementations. Through a comprehensive examination of DFA theory and
practical considerations, this report aims to provide valuable insights for researchers,
practitioners, and enthusiasts in the field of automata theory.
2. Introduction:
o DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of
the computation. The finite automata are called deterministic finite automata if the
machine is read an input string one symbol at a time.
o In DFA, there is only one path for specific input from the current state to the next
state.
o DFA does not accept the null move, i.e., the DFA cannot change state without any
input character.
o DFA can contain multiple final states. It is used in Lexical Analysis in Compiler.
In the following diagram, we can see that from state q0 for input a, there is only one path
which is going to q1. Similarly, from q0, only one path for input b goes to q2.
3 Procedure and Discussion
❖ FORMAL DEFINITION OF DFA:
A DFA is a collection of 5-tuples same as we described in the definition of FA.

1. Q: finite set of states
2. ∑: a finite set of the input symbol
3. q0: initial state
4. F: final state
5. δ: Transition function
The transition function can be defined as:
1. δ: Q x ∑→Q
❖ GRAPHICAL REPRESENTATION OF DFA:
A DFA can be represented by digraphs called state diagrams. In which:
1. The state is represented by vertices.

2. The arc labeled with an input character shows the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by a double circle.
Example :
5. Q = {q0, q1, q2}
6. ∑ = {0, 1}
7. q0 = {q0}
8. F = {q2}
Solution:
Transition Diagram:
Transition Table:
Present State Next state for Input 0 Next State of Input 1
→q0 q0 q1
q1 q2 q1
*q2 q2 q2
❖ CONSTRUCTION OF DFA
TYPE-01 PROBLEMS-
In Type-01 problems, we will discuss the construction of DFA for languages consisting of strings ending
with a particular substring.
STEPS TO CONSTRUCT DFA-

Following steps are followed to construct a DFA for Type-01 problems-
Step-01:
• Determine the minimum number of states required in the DFA.
• Draw those states.
• Use the rule to determine the minimum number of states-Calculate the length of substring. All
strings ending with ‘n’ length substring will always require minimum (n+1) states in the DFA
Step-02:
• Decide the strings for which DFA will be constructed.
Step-03:
• Construct a DFA for the strings decided in Step-02.
Remember the following rule while constructing the DFA-Always prefer to use the existing path.
Create a new path only when there exists no path to go with.
Step-04:
• Send all the left possible combinations to the starting state.
• Do not send the left possible combinations over the dead state.
PROBLEM-01:
Draw a DFA for the language accepting strings ending with ’01’ over input alphabets ∑ = {0, 1}
SOLUTION-
Regular expression for the given language = (0 + 1)*01
Step-01:
• All strings of the language ends with substring “01”.
• So, length of substring = 2.
Thus, Minimum number of states required in the DFA = 2 + 1 = 3.
It suggests that minimized DFA will have 3 states.
Step-02:
We will construct DFA for the following strings-
• 01
• 001
• 0101
Step-03: The required DFA is-
TYPE-02 PROBLEMS-
In Type-02 problems, we will discuss the construction of DFA for languages consisting of strings starting with a
particular substring.
STEPS TO CONSTRUCT DFA-

Following steps are followed to construct a DFA for Type-02 problems-
Step-01:
• Determine the minimum number of states required in the DFA.
• Draw those states.
• Use the rule to determine the minimum number of states-Calculate the length of substring.
All strings starting with ‘n’ length substring will always require minimum (n+2) states in the DFA.
Step-02:
• Decide the strings for which DFA will be constructed.
Step-03:
• Construct a DFA for the strings decided in Step-02.
Remember the following rule while constructing the DFA-
• Always prefer to use the existing path.
• Create a new path only when there exists no path to go with.
Step-04:
• Send all the left possible combinations to the dead state.
• Do not send the left possible combinations over the starting state.
PROBLEM-02:
Draw a DFA for the language accepting strings starting with ‘ab’ over input alphabets ∑ = {a, b}
Solution-
Regular expression for the given language = ab(a + b)*
Step-01:
• All strings of the language starts with substring “ab”.
• So, length of substring = 2.
Thus, Minimum number of states required in the DFA = 2 + 2 = 4.

It suggests that minimized DFA will have 4 states.
Step-02:
We will construct DFA for the following strings-
• ab
• aba
• abab
Step-03:
The required DFA is--
Practical Applications:
1.Pattern Recognition Examine how DFAs are employed in pattern recognition tasks, such as string
matching and DNA sequence analysis.
2.Lexical Analysis Discuss the role of DFAs in lexical analysis and tokenization within compiler design.
3.Real-world Implementations Highlight specific instances of DFA applications in diverse fields,

showcasing their versatility and effectiveness.
Challenges and Limitations:

1.Complexity Issues Address the computational complexities associated with DFAs and situations where
non-deterministic automata may be more suitable.
2.Handling Non-Regular Languages Discuss the limitations of DFAs in representing non-regular languages
and potential alternative solutions.
4.Conclusion:
In conclusion, this technical report has delved into the realm of deterministic finite automata (DFA),
providing a comprehensive understanding of their fundamental concepts, structure, and applications. We
explored the theoretical underpinnings of DFAs, emphasizing their deterministic nature and finite state
representation. Additionally, practical examples and real-world applications were examined to highlight the
versatility and relevance of DFAs in various domains, including pattern recognition, lexical analysis, and
language processing.
Through the exploration of DFA design principles and the analysis of their computational capabilities, it is
evident that DFAs offer a powerful and efficient approach for solving specific classes of problems. The
report has also discussed the limitations and challenges associated with DFAs, such as their inability to
handle certain complex patterns or efficiently represent non-regular languages.
In summary, this report has provided a thorough exploration of deterministic finite automata, offering a
foundation for further research and practical implementations. As we continue to push the boundaries of
computational systems, the knowledge gained from understanding DFAs will undoubtedly contribute to the
development of more sophisticated and efficient solutions in the realm of automata theory and beyond.
5 .References:
1. Introduction to Automata Theory, Languages, and Computation, by John E. Hopcroft, Rajeev Motwani.
2. Theory of Computer Science: Automata, Languages, and Computation, by K.L.P Mishra
and N. Chandrasekaran
Third Edition, 2006.
Page 3

Piyush Kumar

Uploaded by

Copyright:

Available Formats

Piyush Kumar

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Piyush Kumar

Uploaded by

Copyright:

Available Formats

Technical Report Writing on

Deterministic Finite Automata

Department of : Computer Science and Engineering

3 Procedure and Discussion

❖ FORMAL DEFINITION OF DFA:

A DFA is a collection of 5-tuples same as we described in the definition of FA.

The transition function can be defined as:

❖ GRAPHICAL REPRESENTATION OF DFA:

A DFA can be represented by digraphs called state diagrams. In which:

1. The state is represented by vertices.

Present State Next state for Input 0 Next State of Input 1

STEPS TO CONSTRUCT DFA-

STEPS TO CONSTRUCT DFA-

Thus, Minimum number of states required in the DFA = 2 + 2 = 4.

3.Real-world Implementations Highlight specific instances of DFA applications in diverse fields,

Challenges and Limitations:

You might also like