A deterministic finite automaton (DFA) is a finite-state machine that accepts or rejects a given string of symbols by running through a state sequence that is uniquely determined by the string in the theory of computation.
For each input symbol, the state to which the machine will move can be determined using DFA. It's called as a Deterministic Automaton as a result of this. As it contains a finite number of states, the machine is called a Deterministic Finite Machine or Deterministic Finite Automaton.
A DFA is a state machine built up of states and transitions that can accept or reject a finite string made up of a series of symbols and evaluate it to a predefined language across a predefined set of characters. We represent states with circles and transitions with directed arrows. Every state must have each symbol radiating from it, or it will not be characterized as a DFA. The machine is known as a Deterministic Finite Machine since it has a finite number of states.
Let us take an example to understand it in a better way:
Consider a machine that accepts strings containing at least one a from the alphabets a and b.
In the above picture, the initial state of the machine is q0, and the final state of the machine is qf, the state which determines whether the string is accepted or not.
Assume we have the string 'ba.'
The letter 'b' is the first to enter the system.
As it can be seen in the diagram above when b enters the system, it is accepted by q0 and remains there. When we give the machine the symbol a, we can see that when q0 accepts a, it proceeds to the final state, qf. (The double circles represent the final state.)
The string a is accepted by the machine and the string has ended, we can conclude that the given string is accepted by the DFA.
Also read - Arden's theorem
Transition table
The transition table is a table that shows how the transition function works. It takes two inputs (a state and a symbol) and outputs a state (the "next state").
The following elements make up a transition table:
The input symbols are represented by columns. States are represented by rows. The next state corresponds to the entries. An arrow with no source denotes the start state. A star indicates the accepted state. The transition table for the same DFA is following:
Present State
Next State from input a
Next State from input b
→q0
qf
q0
*qf
qf
qf
Need of Deterministic Finite Automata
DFAs make it much easier to use certain projects and applications that switch between valid and invalid states. DFAs are useful in the functionality of applications such as
Design a DFA over the input alphabets {a,b} which accepts all strings that end with a.
Step 1: Consider the strings {a,aa,ba,aba,bba………} that follow the above condition.
We can derive from the preceding example that any number of alphabets can come before a.
Step 2: Design the DFA for the lowest possible string.
As we can see, in order to answer the question, we need a machine that accepts strings that end in a, it doesn’t matter what is the starting of the string, only the ending string should be a. Because our condition only involves one symbol, we have only one necessary transition, so we take two states. In this case, the string can begin with any symbol but must end with an a. As a result, any presence of b is directed to q0, which is our initial state, whereas a's are directed to the final state qf, which is the final state of the DFA.
The transition table for the above DFA is as followed:
Present State
Next State from input a
Next State from input b
→q0
qf
q0
*qf
qf
q0
Dead state in DFA
If the machine has successfully progressed to the final string accepting state, we can say that the string has been accepted by the DFA.
However, if we arrive at a point where the machine can no longer progress to its final state, we have arrived at a dead state. A Dummy state is another name for a dead state.
Let us look at the following example to understand the dead state in a better way
In this example, the machine will begin, and if we want to read strings that begin with 0, the machine will reach its final state B, which will allow it to accept a string.
However, if we start the machine with 1, it will not be able to advance to the final state. It will reach another intermediate state which is C. We are now in a dead state after reading 1. And the string will not be accepted by DFA.
The transition table for the above DFA is as followed:
Deterministic Finite Automata (DFA) are used in various applications across computer science and related fields due to their ability to model and recognize patterns defined by regular languages. Here’s how DFA can be effectively utilized:
Pattern Matching: DFA can be employed to search for specific patterns within strings or texts efficiently. By constructing a DFA that represents the pattern to be found, you can traverse the input text and determine if the pattern exists, and where it occurs.
Lexical Analysis: DFA are extensively used in compilers and interpreters for lexical analysis, also known as tokenization. Tokens such as keywords, identifiers, operators, and literals in programming languages are typically recognized using DFA. Each token type is represented by a DFA that defines its structure and rules.
String Validation: DFA can verify whether a given string adheres to a specified format or syntax. For instance, validating email addresses, phone numbers, URLs, or any structured data format can be efficiently handled using DFA.
Finite State Machines (FSM): DFA serve as the fundamental building blocks for designing more complex finite state machines. FSMs are widely used in control systems, protocol design, circuit design, and modeling sequential logic.
Regular Expression Matching: DFA can be implemented as part of engines that process regular expressions. Regular expressions define patterns that describe sets of strings, and DFA can recognize these patterns efficiently.
In practice, DFA are implemented programmatically using states, transitions, and an input alphabet. They offer fast processing times and deterministic behavior, making them suitable for real-time systems and applications requiring efficient pattern recognition and validation.
Converting NFA to DFA
We'll go over how to convert NFA to its DFA equivalent in this section. The machine changes states when a specific input is supplied to the current state in NFA. It can have zero, one, or several motions on a single input symbol. In DFA, however, when a specific input is given to the current state, the machine only goes to one state. DFA can only make one move on each input symbol.
Suppose M is an NFA denoted by M = (Q, ∑, δ, q0, F). We need to create an DFA M' = (Q', ∑', q0', δ', F') such that L(M) = L(M').
Follow the below steps to convert the NFA to dfa:
Initially Q' = Ï•
Add q0 to Q’
Loop over each of the states in Q’ and for each possible input, find the set of states after the transition
The final state of the DFA will be all the state containing F which is the final state of NFA M.
Example:
State
a
b
q0
q1, q2
q1
q2
q1, q2
q2
Step 1:
The initial start state of the DFA will be Q’. Initially Q’ = {q0}
The state q0 on input a goes to both the state q0 and q1, hence we form a new state {q0,q1}
State
a
b
{q0}
{q1, q2}
Step 2:
Now we define transition for our new state {q1,q2}. q2 on a goes to q2 and q1 and q2 on b go to q2. Hence adding the transitions.
State
a
b
{q0}
{q1, q2}
{q1, q2}
{q1, q2}
{q2}
Step 3:
Now we define transition for our new state {q2}. Hence after adding the transitions, we get.
State
a
b
{q0}
{q1, q2}
{q1, q2}
{q1, q2}
{q2}
{q2}
{q1,q2}
{q2}
Hence our final state will be {q1,q2} and start state will be {q0}.
A Deterministic Finite Automaton (DFA) has a finite set of states, a single initial state, a finite input alphabet, and a transition function that uniquely determines the next state for each input symbol. It also has a set of accept states where the machine halts.
Can DFA have multiple final states?
Yes, a DFA can have multiple final states. The string is accepted if it leads to any of these final states after processing all input symbols. This flexibility allows DFAs to recognize a broader range of languages and patterns.
Can DFA be converted to NFA?
Yes, any DFA can be transformed into (and is already) an NFA.
Which language is accepted by deterministic finite automata?
A language L is accepted by a DFA < Q , , q0 , , A > , if and only if L = { w | *( q0 , w ) A } . That is, the language accepted by a DFA is the set of strings accepted by the DFA.
Conclusion
This article has covered a detailed explanation of Deterministic Finite Automata (DFA) and how it can be converted into Non-deterministic Finite Automata (NFA). We hope this information has helped you understand DFA better. Check out more of our DFA articles for further learning, and please support us by upvoting our blog to help others learn too.
46+ registered 