Example 1.6.8 Define DFA.
Design a DFA to accept the binary numbers which
are divisible by 5.
Solution: i) DFA - Refer section 1.6.
ii) DFA for divisibility by 5: For designing DFA as a divisibility by 5 tester for a
binary string we will consider following states.
q0 - remainder 0 state
q1 - remainder 1 state
q2 - remainder 2 state
q3 - remainder 3 state
q4 - remainder 4 state
Now we will design DFA by considering above states and finding next states with
input 0 and 1.
The DFA will be
Simulation: Consider the string (1111)2 = (15)10
q0 Ⱶ 1111
1q1 Ⱶ 111
11q3 Ⱶ 11
111q2 Ⱶ 1
1111q0 Ⱶ
Divisible by 5. q0 is a final state.
Consider input string (1110) = (14)10
q0 Ⱶ 1110
1 q1 Ⱶ 110
11 q3 Ⱶ 10
111 q2 Ⱶ 0
1110 q4 Ⱶ
Remainder 4. q4 is remainder 4 state.
QUES : Construct a Deterministic Finite State Automata that accepts the set of strings
over {a,b} having an even number of a’s and odd number b’s, even number of a’s and
even number of b’s, odd number a’s and even number b’s and odd number a’s and odd
number of b’s.
This DFA needs 4 states to track the parity (even/odd) of 'a's and 'b's:
q0 (EaEb) for Even 'a's/Even 'b's (Start/Final),
q1 (EaOb) for Even 'a's/Odd 'b's (Final),
q2 (OaEb) for Odd 'a's/Even 'b's, and
q3 (OaOb) for Odd 'a's/Odd 'b's,
with transitions changing states based on the input character (a or b), accepting strings
with any combination of even/odd counts for both 'a's and 'b's, meaning all states are
final because the description covers all parity possibilities.
DFA Definition
States (Q): {q0, q1, q2, q3}
Alphabet (Σ): {a, b}
Start State (q0): q0
Final States (F): {q0, q1, q2, q3} (All states are final as the language accepts
all parity combinations)
Transitions (δ):
States Input 'a' Input 'b'
q0 (EaEb) q2 (OaEb) q1 (EaOb)
q1 (EaOb) q3 (OaOb) q0 (EaEb)
q2 (OaEb) q0 (EaEb) q3 (OaOb)
q3 (OaOb) q1 (EaOb) q2 (OaEb)
State Meanings & Logic
q0 (EaEb): Even 'a's, Even 'b's (Start).
q1 (EaOb): Even 'a's, Odd 'b's.
q2 (OaEb): Odd 'a's, Even 'b's.
q3 (OaOb): Odd 'a's, Odd 'b's.
Transitions:
An 'a' flips the 'a' parity (Ea -> Oa, Oa -> Ea).
A 'b' flips the 'b' parity (Eb -> Ob, Ob -> Eb).
Why all states are fi nal:
The question asks for strings with:
1. Even 'a's & Odd 'b's (q1)
2. Even 'a's & Even 'b's (q0)
3. Odd 'a's & Even 'b's (q2)
4. Odd 'a's & Odd 'b's (q3)
Since this covers all possible parity combinations for 'a' and 'b', any string will
end in one of these states, and thus all states must be accepting.
Example 1.6.11 Give deterministic finite automata accepting the following
language over the alphabet.
1) Number of 1's is a multiple of 3.
Solution: 1) We assume alphabet as input set Σ = {1}
2) Number of 1's is not a multiple of 32) For recognizing number of 1's not a
multiple of 3, we will use the DFA in step (1). That means we will make non final
states as final and final state as non-final ones. The DFA will then be as shown in
figure.
Example 1.7.2 Draw state transition diagram for NFA over {a, b} containing
substring aabb.
Solution: The FA can be
Ques: An NFA is constructed to accept strings where two 0's are separated by a string
of length 4i, for some i ≥ 0.
An NFA accepting the set of strings {0,1}*
To construct an NFA that accepts the set of strings where two 0's are separated by a
string whose length is 4i, for some i ≥ 0, follow the steps:
To solve the first part of the problem, we need to construct a NFA for the
language over the alphabet ∑ = {0,1} such that two 0's are separated by a string
whose length is 4i for some i>=0 .
This means there should be a sequence of 4, 8, 12, etc., characters (comprised of
any combination of 0's and 1's) between two consecutive 0's.
Step-by-Step NFA Construction:
1. States and Transitions:
o Start with an initial state .
o Move from q0 to q1 on reading a '0'.
o From q1 , move to an intermediate state q2 through four
states q1,q2,q3,q4 by consuming exactly four inputs, either '0' or '1'.
o Use non-deterministic transitions that allow you to loop back to q1 from
q2 , ensuring the length of the separating string can be a multiple of 4.
o Finally, transition back to q5 after a subsequent '0'.
2. Final States:
o The final state is any state that results after reading a '0' separated by
strings of the length meeting the requirement.
This completes an NFA representation for the desired language. It's important to
recognize that the flexibility of NFAs allows multiple paths to handle these transitions,
demonstrating their non-deterministic nature.
Finite Automata with Epsilon Transitions (ε-NFA)
• The ɛ-transitions in NFA are given in order to move from one state to another
without having any symbol from input set Σ.
Definition of NFA with ε
The language L accepted by NFA with ε, is represented as
M = (Q, Σ, δ, q0, F) be a NFA with ε. Where
Q is a finite set of states.
Σ is input set.
δ is a transition or a mapping function for transitions from Q×{ΣUε} to P(Q).
q0 is a start state.
F is a set of final states such that F ϵ Q.
epsilon closure
The ε closure(P) is a set of states which are reachable from state P on ε-transitions.
ε-closure (P) = P, where P ∈ Q
The epsilon closure is as mentioned below −
If there exists ε-closure (P) = {q} and ?(q, ε) =r then, ε-closure (P) = {q, r}
Example - Find ε-closure for the following NFA with epsilon.
ε-closure (q0)= {q0,q1,q2}
self state+ ε-reachable states.
ε-closure (q1)= { q1,q2}
q1 is self-state and q2 is a state obtained from q1 with epsilon input.
ε-closure (q2)= {q2}
Example - Find the number of epsilon closure in the below diagram.
The epsilon closure set of f2 consist of the elements − {f2, f3}, set of f1 consist of the
elements − {f1}. Therefore, the count of the element in the closure set is 2.
Consider the NFA with ɛ as:
• In this NFA with ε, q0 is a start state with input 0 one can be either in state q o or in
state q1. If we get at the start a symbol 1 then with ε - move we can change state from
q0 to q1 and then with input we can be in state q1.
• On the other hand, from start state q0, with input 1 we can reach to state q2.
• Thus it is not definite that on input 1 whether we will be in state q1 or q2. Hence it is
called NFA and since there are some ε moves by which we can simply change the
states from one state to other. Hence it is called NFA with ε.
Example 1.8.1 Construct NFA with ε which accepts a language consisting the strings of
any number of a's followed by any number of b's. Followed by any number of c's.
Solution: Here any number of a's or b's or c's means zero or more in number. That
means there can be zero or more a's followed by zero or more b's followed by zero or
more c's. Hence NFA with ε can be -
Normally ε's are not shown in the input string. The transition table can be -
We can parse the string aabbcc as follows -
δ (q0, aabbcc) Ⱶ δ (q0, abbcc)
Ⱶ δ (q0, bbcc)
Ⱶ δ (q0, εbbcc)
Ⱶ δ (q1, bbcc)
Ⱶ δ (q1, bcc)
Ⱶ δ (q1, cc)
Ⱶ δ (q1, εcc)
Ⱶ δ (q2, cc)
Ⱶ δ (q2, c)
Ⱶ δ (q2, ε)