1.
Design a finite automata which accepts odd number of 0’s and 1’s over input alphabet Σ =
{0,1}.
Solution: Given language L= {01,000111, 0000011111, …..}
M= {Q, Σ, δ, q0, F}
Q= {A, B, C, D}
Σ= {0,1}
q0= {A}
F={C}
Transition Diagram:
Transition table:
States 0 1
->A B D
B A C
*C D A
D C B
Check the acceptance of the string:
The string 010101 can be processed on generated finite automata as follows:
A-0 B--1 C-0-- D---1 A----0 B—1 C
C is a final state so the string is accepted.
Hence the constructed Finite automata is correct.
2. Construct a DFA to accept the binary string divisible by 5?
Solution: Given Binary number Σ= {0,1}
The possible number divisible by 5 are remainders are (0,1,2,3,4)
The binary number for 0 – 0000
The binary number for 1 - 0001
The binary number for 2 - 0010
The binary number for 3 - 0011
The binary number for 4 – 0100
Transition table:
State 0 1
->*A A B
B C D
C E A
D B C
E D E
Transition Diagram:
M= {Q, Σ, δ,q0,F}
Q={A, B ,C,D,E}
Σ= {0,1}
q0= {A}
F={A}
Let us check the acceptance of the string: 101
A-1-- B-0-- C--1- A
A is a final state so the string is accepted.
The given string is accepted by the DFA.
Hence the constructed Finite automata is correct.
3. Convert the following NFA into its equivalent DFA
Solution: Given Q= {q0, q1, q2}
Initial state = ->q0
Final state= *q2
Σ= {0,1}
Transition Table NFA
δ 0 1
{q0, q1} q0
q0
q1 ∅ q2
*q2 ∅ ∅
By using transition table of NFA we can constructed DFA.
δ 0 1
q0 {q0, q1} q0
{q0,q1} {q0, q1} {q0,q2}
{q0,q2} {q0,q1} q0
By using transition table we have constructed DFA.
By observing DFA we can construct DFA transition diagram:
Let us check the acceptance of the string: 101
q0-1-- q0-0-- {q0, q1}--1- {q0,q2}
{q0, q2} is a final state so the string is accepted.
The given string is accepted.
[Link] between NFA and DFA?
Solution:
DFA NFA
1. Deterministic finite Non -Deterministic finite
automata automata
2. Each transition leads to Transition leads to a subset of
exactly one state called as state that is some transition can be
deterministic finite non-deterministic.
automata.
3. Empty strings transitions are Permit empty string transitions.
not allowed.
4. Accepts the input with the Accept the input if one of the last
last states is in finite state. state is final state.
5. Requires more space. Every NFA is not DFA.
6. DFA is more difficult to NFA is easier to construct
construct than NFA.
7. Every DFA is said to be Every NFA is not DFA.
NFA
8. Q* Σ->Q Q* Σ->2Q
5. Convert the following NFA with E into its equivalent NFA with out ϵ.
Solution: ϵ- closure of all the states is given as:
ϵ- closure (A) = {A, B, C}
ϵ- closure (B) = {B, C}
ϵ- closure (C) = {C}
Transition function is determined as follows,
δ1 (A, ϵ) = ϵ- closure (A) = {A, B, C}
δ1 (A, a) = ϵ- closure (δ (δ (A, ϵ), a)
= ϵ- closure (δ {A, B, C}, a))
= ϵ- closure ((δ (A, a) U δ (B, a) U δ (C, a))
= ϵ- closure (∅ U B U B)
= ϵ- closure(B)
= {B, C}
δ1 (A, b) = ϵ- closure (δ (δ (A, ϵ), a)
= ϵ- closure(δ{A,B,C},b))
= ϵ- closure ((δ (A,b) U δ(B,b) U δ(C,b))
= ϵ- closure (A U ∅ U A)
= ϵ- closure(A)
= {A, B, C}
δ1 (B, a) = ϵ- closure (δ (δ (B, ϵ), a)
= ϵ- closure (δ {B, C}, a))
= ϵ- closure ((δ (B,a) U δ(B,b) U δ(C,a))
= ϵ- closure (B U B)
= ϵ- closure(B)
= {B, C}
δ1 (B, b) = ϵ- closure (δ (δ (B, ϵ), b)
= ϵ- closure ((δ {B, C}, b))
= ϵ- closure ((δ (B,b) U δ(C,b))
= ϵ- closure (∅ U A)
= ϵ- closure(A)
= {A, B, C}
δ1 (C,a)= ϵ- closure (δ (δ(C, ϵ),a)
= ϵ- closure(δ{C}, a))
= ϵ- closure((δ(C,a))
= ϵ- closure(B)
= {B, C}
δ1 (C, b) = ϵ- closure (δ (δ(C, ϵ),b)
= ϵ-closure(δ{C}, b))
= ϵ- closure((δ(C,b))
= ϵ- closure(A)
= {A, B, C}
Transition table for NFA is:
States a b
{B, C} {A, B, C}
*A
*B {B, C} {A, B, C}
*C {B, C} {A, B, C}
Transition diagram of NFA without ϵ-transition is:
6. Design NFA to accept strings with a’s and b’s such that the string end with
bb?
Solution: The given language L= {abb, ababb, abaaabb, …..}
Let the NFA be M = {Q, Σ, δ, q0, F}
Where,
Set of states (Q) = {A, B, C}
Set of input symbol (Σ) = {a, b}
The transition diagram (NFA) that accepts set of strings with ‘a’s and ‘b’s such that the string
end with bb is as follows.
Here,
Initial state (q0) = A
Final state, (F) = C
The transition table (δ) is shown below,
Table: Transition Table
State
a b
→A A {A,B}
B – C
*C A C
Let us check the acceptance of the string for abb
A—a A---b- B—b- C
C is the Final state so the given string is accepted.
Hence the given NFA is accepted.
7. Design a DFA for the following over {a,b}
a) All strings containing not more than 3a’s?
Solution: The given language L= {aaa,baaab,bbaaa,…….}
Given Q={q0, q1,q2,q3,q4}
Initial state =q0
Σ={a,b}
B) All strings that has at least two occurrences of b between any two occurrences of a.
Solution: The given language L= {aabbaa, baabbaab, bbaaa,…….}
Given Q={q0,q1,q2,q3,q4,q5}
Initial state =q0
Σ={a,b}
[Link] finite Automata? Explain the structure of finite automata?
Solution:
It is the study of abstract computing machines. The main goal is used to describe the
boundary between what a computing machine should do and what it cannot do.
There are two types of finite automata:
● Deterministic Finite Automata (DFA)
● Non-Deterministic Finite Automata (NFA)
A finite automaton consists of 5 tuples:
{Q, Σ, q, F, δ}, where:
● Q: Finite set of states
● Σ: Set of input symbols
● q: Initial state
● F: Set of final states
δ: Transition function
Structural representation of finite automata:
[Link] input tape is divided into cells and each cell contains one symbol from the input
alphabet.
[Link] symbol ψ is used at the leftmost cell and symbol $ is used at the rightmost cell to
indicate the beginning and end of the input tape.
[Link] head reads one symbol on the input tape & finite control controls the next
configuration.
[Link] head can read either from left-to-right or from right-to-left one cell at a time. The head
can’t write and can’t move backward.
1. What is a string? Write about the concatenation of two strings?
Solution: A string is a finite sequence of symbols drawn from alphabet is knowns as
string. String is denoted by w.
W = abcd
|w|= 4 (represents length of a string)
Concatenation of string: Concatenation of two languages L1and L2 denoted as L1L2 .
L1 = ab
L2= cd
L1L2 = abcd.
2. Define Alphabet and Language?
Solution: Alphabet: An Alphabet or character is a non-empty finite set of symbols.
It is denoted by Σ (Sigma).
Σ= {0,1}.
Language: The language is denoted by L is a set of strings over alphabet Σ.
Example: Language L= {01,00011, 111000, ….}
3. Define DFA?
Solution: A Deterministic Finite Automaton (DFA) is a mathematical model, or a type of
finite-state machine, that accepts or rejects an input string by processing it one symbol at
a time through a unique sequence of states.
DFA consists of 5 tuples {Q, Σ, q, F, δ}.
Q : set of all states.
Σ : set of input symbols. (Symbols which machine takes as input )
q : Initial state. (Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.
[Link] Kleene Closure?
Solution: The Kleene closure, denoted as L* or L*, is the set of all strings formed by
concatenating zero or more strings from L.
Example: L = {a, b}, then L* = {ε, a, b, aa, ab, ba, bb, aaa, ...}.
[Link] Transition Diagram?
Solution: A transition diagram describes the behaviour of the finite automata. It consists
of nodes or circles called states and directed line segments between each state called node
edges.