Formal Languages and Automata Theory, chapter2

Finite Automata (DFA& NFA)

Introduction
 An automaton with a finite number of states is called a Finite Automaton (FA) or Finite
State Machine (FSM).
 Informally, a state diagram that comprehensively captures all possible states and transitions
that a machine can take while responding to a stream or sequence of input symbols.
 An automaton can be represented by a 5-tuple (Q, Σ, δ, q0, F), where −
1. Q is a finite set of states.
2. Σ is a finite set of symbols, called the alphabet of the automaton.
3. δ is the transition function.
4. q0 is the initial state from where any input is processed (q0 ϵ Q).
5. F is a set of final state/states of Q (F ϵ Q).
 Finite Automaton can be classified into two types −
1. Deterministic Finite Automaton (DFA)
2. Non-deterministic Finite Automaton (NDFA / NFA)

Deterministic Finite Automaton (DFA)

 In DFA, for each input symbol, one can determine the state to which the machine will move.
Hence, it is called Deterministic Automaton. As it has a finite number of states, the
machine is called Deterministic Finite Machine or Deterministic Finite Automaton.

Formal Definition of a DFA

 A DFA can be represented by a 5-tuple (Q, Σ, δ, q0, F) where −

1. A finite set of states, often denoted Q
2. A finite set of input symbols, often denoted Σ
3. A transition function that takes as arguments a state and an input symbol and returns a
state.
The transition function is commonly denoted δ

1
 Formal Languages and Automata Theory, chapter2

If q is a state and a is a symbol, then δ (q, a) is a state p (and in the graph that represents
the automaton there is an arc from q to p labeled a) Q x Σ ==> Q
4. A start state, one of the states in Q
5. A set of final or accepting states F (F ⊆ Q)

Notations for DFAs

1. Transition diagrams
 Each state is a node
 For each state q ∈ Q and each symbol a ∈ Σ, let δ(q, a) = p
 Then the transition diagram has an arc from q to p, labeled a
 There is an arrow to the start state q0
 Nodes corresponding to final states are marked with doubled circle
2. Transition tables
 Tabular representation of a function
 The rows correspond to the states and the columns to the inputs
 The entry for the row corresponding to state q and the column corresponding
to input a is the state δ(q, a)

Graphical Representation of a DFA

 A DFA is represented by digraphs called state diagram.

 The vertices represent the states.
 The arcs labeled with an input alphabet show the transitions.
 The initial state is denoted by an empty single incoming arc.
 The final state is indicated by double circles.
 Example
 Let a deterministic finite automaton be →
Q = {q0,q1,q2},
Σ = {0, 1},
q0 = { q0},
F = { q2}, and

2
 Formal Languages and Automata Theory, chapter2

Transition function δ as shown by the following table –

Present State Next State for Next State for

Input 0 Input 1
q0 q1 q0

q1 q1 q2

q2 q2 q2

Its graphical representation would be as follows –

 The DFA define a language: the set of all strings that result in a sequence of state transitions
from the start state to an accepting state

Extended transition function

 Describes what happens when we start in any state and follow any sequence of inputs
 If δ is our transition function, then the extended transition function is denoted by ˆδ
 The extended transition function is a function that takes a state q and a string w and returns a
state p (the state that the automaton reaches when starting in state q and processing the
sequence of inputs w)

3
 Formal Languages and Automata Theory, chapter2

What does a DFA do on reading an input string?

 Input: a word w in Σ*
 Question: Is w acceptable by the DFA?
 Steps:
o Start at the “start state” q0
o For every input symbol in the sequence w do
 Compute the next state from the current state, given the current input
symbol in w and the transition function
o If after all symbols in w are consumed, the current state is one of the accepting
states (F) then accept w;
o Otherwise, reject w.
Language of a DFA
 A DFA A accepts string w if there is a path from q0 to an accepting (or final) state that is
labeled by w
 i.e., L(A) = { w | ^δ(q0,w) ϵ F }
 I.e., L(A) = all strings that lead to an accepting state from q0.

Non-deterministic Finite Automata (NFA)

 In NDFA, for a particular input symbol, the machine can move to any combination of the
states in the machine.
 In other words, the exact state to which the machine moves cannot be determined.
 Hence, it is called Non-deterministic Automaton.
 As it has finite number of states, the machine is called Non-deterministic Finite
Machine or Non-deterministic Finite Automaton.
 Transitions could be non-deterministic.

 Each transition function therefore maps to a set of states

 A NFA has the power to be in several states at once

4
 Formal Languages and Automata Theory, chapter2

 This ability is often expressed as an ability to “guess” something about its input
 Each NFA accepts a language that is also accepted by some DFA
 NFA are often more succinct and easier than DFAs
 We can always convert an NFA to a DFA, but the latter may have exponentially more
states than the NFA (a rare case)
 The difference between the DFA and the NFA is the type of transition function δ
o For a NFA δ is a function that takes a state and input symbol as arguments (like
the DFA transition function), but returns a set of zero or more states (rather than
returning exactly one state, as the DFA must)
A Non-deterministic Finite Automaton (NFA) consists of:
 Q ==> a finite set of states
 Σ ==> a finite set of input symbols (alphabet)
 q0 ==> a start state
 F ==> set of accepting states
 δ ==> a transition function, which is a mapping between Q x Σ ==> subset of Q
 An NFA is also defined by the 5-tuple: {Q, Σ, q0, F, δ }
 Example
 Let a deterministic finite automaton be →
Q = {q0,q1,q2},
Σ = {0, 1},
q0 = { q0},
F = { q2}, and

Transition function δ as shown by the following table –

Present State Next State Next State
for Input 0 for Input 1
q0 {q0 ,q1 } {q0 }

q1 ∅ {q2 }

q2 {q2} {q2}

5
 Formal Languages and Automata Theory, chapter2

Its graphical representation would be as follows –

How to use an NFA?

 Input: a word w in ∑*
 Question: Is w acceptable by the NFA?
 Steps:
o Start at the “start state” q0
o For every input symbol in the sequence w do
o Determine all possible next states from all current states, given the current input
symbol in w and the transition function
o If after all symbols in w are consumed and if at least one of the current states is a
final state then accept w;
o Otherwise, reject w.
The Language of a NFA
 The language of a NFA
A = (Q, Σ, δ, q0, F), denoted L(A) is defined by L(A) = {w | ˆδ(q0,w) ∩ F ≠ ∅}
 The language of A is the set of strings w ∈ Σ* such that ˆδ(q0,w) contains at least one
accepting state
 The fact that choosing using the input symbols of w lead to a non-accepting state, or do
not lead to any state at all, does not prevent w from being accepted by a NFA as a whole.

6
 Formal Languages and Automata Theory, chapter2

DFA vs NDFA
The following table lists the differences between DFA and NDFA.

DFA NDFA
The transition from a state is to a single The transition from a state can be to multiple
particular next state for each input symbol. next states for each input symbol. Hence it is
Hence it is called deterministic. called non-deterministic.

Empty string transitions are not seen in DFA. NDFA permits empty string transitions.
For each state, transition on all possible Not all symbol transitions need to be defined
symbols (alphabet) should be defined explicitly
Backtracking is allowed in DFA In NDFA, backtracking is not always
possible.
Requires more space. Requires less space.
A string is accepted by a DFA, if it transits to A string is accepted by a NDFA, if at least
a final state. one of all possible transitions ends in a final
state.

Equivalence of DFA & NFA

Theorem:
A language L is accepted by a DFA if and only if it is accepted by NFA.
Proof:
1. If part:
 Prove by showing every NFA can be converted to an equivalent DFA (in the next
few slides…)
2. Only-if part is trivial:
 Every DFA is a special case of an NFA where each state has exactly one
transition for every input symbol.
 Therefore, if L is accepted by a DFA, it is accepted by a corresponding NFA.
Proof for the if-part
 If-part: A language L is accepted by a DFA if it is accepted by an NFA

7
 Formal Languages and Automata Theory, chapter2

rephrasing…
 Given any NFA N, we can construct a DFA D such that L(N)=L(D).
How to convert an NFA into a DFA?
 Observation: In an NFA each transition maps to a subset of states.
 Represent each “subset of NFA_states”  as a single “DFA_state”.
 We will call this process as Subset construction
 We have a NFA N = (QN , Σ, δN, q0, FN )
The goal is the construction of a DFA D = (QD, Σ, δD, {q0}, FD) such that
L(D) = L(N).
 Construction:
a. QD= all subsets of QN (i.e., power set)
b. FD=set of subsets S of QN s.t. S∩FN≠Φ
c. δD: for each subset S of QN and for each input symbol a in ∑:

 δD(S, a) = U p in s δN (p, a)

NFA to DFA conversion

Algorithm

Input − An NDFA

Output − An equivalent DFA

Step 1 − Create state table from the given NDFA.

Step 2 − Create a blank state table under possible input alphabets for the equivalent DFA.

Step 3 − Mark the start state of the DFA by q0 (Same as the NDFA).

Step 4 − Find out the combination of States {Q0, Q1,... , Qn} for each possible input alphabet.

Step 5 − Each time we generate a new DFA state under the input alphabet columns, we have
to apply step 4 again, otherwise go to step 6.

8
 Formal Languages and Automata Theory, chapter2

Step 6 − The states which contain any of the final states of the NDFA are the final states of
the equivalent DFA.

NFA to DFA construction: Example

NFA:

 Transition table for given NFA

 form the given NFA QN = {q0, q1, q2}

 the subset of states we can define from the QN is QD = {∅, {q0}, {q1}, {q2}, {q0, q1} . .
.}, i.e., QD has 8 states (each one corresponding to a subset of QN )
 To find the states which we can use in DFA we follow the process
o Enumerate all possible subsets
o Determine transitions
o Retain only those states reachable from {q0}

9
 Formal Languages and Automata Theory, chapter2

 The transitions possible are

 The DFA is

10
 Formal Languages and Automata Theory, chapter2

FA with Ԑ-Transitions
 We allow now a transition on Ԑ, i.e., the empty string
 A NFA is allowed to make a transition spontaneously, without receiving an input symbol
 This capability does not expand the class of languages that can be accepted by finite
automata, but it does give us some added programming convenience.
 Definition: Ԑ -NFAs are those NFAs with at least one explicit Ԑ-transition defined.
 Ԑ -NFAs have one more column in their transition table
Example
 L = {w | w is empty, or if non-empty will end in 01}

 Ԑ-closure of a state q, ECLOSE (q), is the set of all states (including itself) that can be
reached from q by repeatedly making an arbitrary number of Ԑ- transitions.
 An Ԑ-NFA A = (Q, Σ, δ, q0, F) where all components have their same interpretation as
for NFA, except that δ is now a function that takes arguments:
1. A state in Q and
2. A member of Σ ∪ {Ԑ}

11
 Formal Languages and Automata Theory, chapter2

We require that Ԑ cannot be a member of Σ

The language of an Ԑ-NFA

 The language of an Ԑ-NFA E = (Q, Σ, δ, q0, F ) is
L(E) = {w | δ ˆ(q0, w) ∩ F ≠∅}

Eliminating Ԑ-Transitions
 Let E = (QE, Σ, δE, q0, FE) be an Ԑ-NFA. Then the equivalent DFA
D = (QD, Σ, δD, qD, FD) is defined as follows:
1. QD is the set of subsets of QE
2. qD = ECLOSE(q0)
3. FD = {S | S is in QD and S ∩ FE ≠∅}
Those sets of states that contain at least one accepting state of E
4. δD (S, a) is computed, for all a in Σ and sets S in QD by:
o Let S = {p1, p2, . . . , pk}

o Compute U i=1 to k δE (pi, a); let this set be {r1, r2, . . . , rm}
o Then δD (S, a) = U j=1 to m ECLOSE(rj)

12