AMERICAN INTERNATIONAL UNIVERSITY-BANGLADESH
CSC3113: THEORY OF COMPUTATION
Lecture: # 3 Week: # 2 Semester: Summer 2024-2025
DETERMINISTIC FINITE
AUTOMATON (DFA)
REGULAR LANGUAGE
Instructor: Dr. Afroza Nahar
Professor, Department of Computer Science,
Faculty of Science and Technology.
afroza@aiub.edu, room no: DN0113 1
LECTURE OUTLINE
Practice Problem with DFA.
Exercise solving from the book.
DFA design Issues.
Regular Language
Closure
Operations
Example: Regular Language closed under Union Operation
CSC3113: Theory of Computation 2
LEARNING OBJECTIVE
Understand, learn & practice with example
Practice designing DFA.
Learn Language, Regular Language & Regular Operations
Analyze Closure under regular Operation
Build one machine from 2 machine using closure under union
CSC3113: Theory of Computation 3
LEARNING OUTCOME
ALL OUTCOME ARE REPRESENTED WITH EXAMPLES
Understand, learn & practice design of DFA.
Analyze and Design new machine model from one or more machine
model(s) using closure rule of regular operation (example: Union).
In doing so, understand that, there are certain cases where DFA
might not give a desired machine model.
CSC3113: Theory of Computation 4
DFA DESIGN ISSUES
The key concept here is to understand the given language.
Type/pattern of input strings that the language gives.
Match the pattern from left to right with the states & transitions of the state
diagram, one by one.
First match the necessary conditions with the transition then complete the
diagram with rest of the transition maintaining the rules.
Maintain the rules –
From each state there must be exactly one transition for each input symbol.
Self-loop represents zero or more number of occurrences of the input symbol.
There can be one or more number of final states .
Make some of your own input strings based on the given language. Few that
should be ACCEPTED and few that should be REJECTED. Test them on your
state diagram after completing or while drawing the state diagram and
update accordingly.
Let us practice some DFA in the following slides.
CSC3113: Theory of Computation 5
DFA: EXAMPLES
1. Draw the state diagram of the DFA for the Language,
L={w | w begins with a 0}, where alphabet is {0, 1}.
2. Draw the state diagram of the DFA for the Language,
L={w | w begins with a 01}, where alphabet is {0, 1}.
3. Draw the state diagram of the DFA for the Language,
L={w | w ends with a 01}, where alphabet is {0, 1}
4. Draw the state diagram of the DFA for the Language,
L={w | w stars and ends with a 01}, where alphabet is
{0, 1}
5. Draw the state diagram of the DFA for the Language,
L={w | w ends with a 11}, where alphabet is {0, 1}
Dr. Afroza Nahar
A5 ={w| w ends with a 0}.
A6 ={w| w begins with a 1}.
A7 ={w| w begins with a 1 and ends with a 0}.
∑ = {0,1} 1
1
0 0
A5 q1 q2
0, 1 q3
0
1 0, 1
A6 q1 q2
0, 1 1
q4
0
1 0
0
A7 q1 q2 q3
1
CSC3113: Theory of Computation 7
5. Draw the state diagram of the DFA for the Language over the
alphabet {0, 1},
a) L = {w | length of w is divisible by 2/multiple of 2/even
length/mode 2
b) Length of string is not divisible by 2 or not multiple of 2, odd
length}
6. Draw the state diagram of the DFA for the Language over the
alphabet is {0, 1}
a) L = {w | w binary number is divisible by 2}
b) L = {w | w binary number is divisible by 3}
Dr. Afroza Nahar
A3 ={w : w is a binary string containing an
odd number of 1s}.
A4 ={w : w is a binary string containing an
even number of 0s using three states}.
∑ = {0,1} 0
0 1
A3 q1 q2
1
1
1 0 1
0
A4 q1 q2 q3
CSC3113: Theory of Computation 9
A8 ={w| w has at least two 1s}.
A9 ={w| w has at most two 1s}.
∑ = {0,1}
0 0 0, 1
1 1
A8 q1 q2 q3
0 0 0
1 1 1
A9 q1 q2 q3 q4 0, 1
10
A10 ={w| w has substring 101}.
A11 ={w| w has substring 011}.
∑ = {0,1}
0 1
A1 1 0 1
q1 q10
0 qs q1 0, 1
0 1
0
1 0
0 1 1
A1 q0 q01
qs q0 0, 1
1 1 1
0
What happens for the language, A11 ={w| w does not have substring 011}?
11
A12={w| each 1 in w is followed by at least one 0}.
A13 ={w | The length of w is at least three and have 0
in 2nd last position}
A14 ={w : The length of w is even and contains 1 in
every odd position}
∑ = {0,1} 0 1 0
A1 1 0 0,1
q2 q3 q4
2 q3
1
1
A1 0, 1 0 0 0
3 q1 q2 q3 q4
1
1
0 1
q5
A1 1
4
1 0, 1 0
q1 q2 q3 q4 0,1
CSC3113: Theory of Computation 12
DESIGNING DFA – EXAMPLE 1
0 Alphabet Σ={0,1,2}.
Language A = {w : the sum of all the symbols in w is
1
a1 1 multiple of 3 }.
Can be represented as follows –
2 S= the sum of all the symbols in w.
If S modulo 3 = 0 then the sum is multiple of 3.
1
2 So the sum of all the symbols in w is 0 modulo 3.
We can model a as state representing
2
0
a0 a2
i
S modulo 3 = i.
The finite state machine M = (Q , Σ, , q , F ), where
1 –
1 1 1 1 1
0
Q = {a ,a ,a },
1 0 1 2
Input example: 01120101 q =a ,
1 0
Present State: F = {a },
1 0
a201 1
Input symbol: | 0 1 2 .
a0 | a0 a1 a2
Accepted
a1 | a1 a2 a0
01120101
ε
CSC3113: Theory of Computation
a2 | a2 a0 a1 13
DESIGNING DFA – EXAMPLE 2
Alphabet Σ={0,1,2}.
1 Language A2 = {w : the sum of all the symbols in
0,2
b0 b1 w is an even number }.
Can be represented as follows –
1 S= the sum of all the symbols in w.
0,2 If S modulo 2 = 0 then the sum is even.
Here, bi is modeled as S modulo 2 = i.
The finite state machine M2= (Q2, Σ, 2, q2, F2),
where –
Q2 = {b0,b1},
q2 = b0,
Input example: 01120101 F2 = {b0},
Present State: 2
b10 |0 1 2 .
b0 | b0 b1 b0
Input symbol: b1 | b1 b0 b1
01120101
ε
Accepted
CSC3113: Theory of Computation 14
REGULAR OPERATIONS
AN ANALOGY
In algebra, we try to identify operations which are common to many
different mathematical structures.
Example:
The integers are closed under –
Addition:
Multiplication:
Negation:
…but NOT Division:
We’d like to investigate similar closure properties of the class of
regular languages
CSC3113: Theory of Computation 15
REGULAR OPERATIONS ON
LANGUAGES
Let be languages.
Union: .
Concatenation:
Star:
Complement:
Intersection:
Reverse:
CSC3113: Theory of Computation 16
REGULAR LANGUAGE
A language is called a regular language if some finite automaton
recognizes it.
Regular Operations: Let A={good, bad}, B = {boy, girl}.
Basic 3 operations used to study the properties of the regular languages
–
Union: AB = {x : x A or x B} = {good, bad, boy, girl}.
Takes all the strings in both A and B and lumps them together into one language.
Concatenation: A B = {xy : x A and y B} = {goodboy, goodgirl, badboy,
badgirl}.
Attaches a string from A in front of a string B in all possible ways to get the strings in
the new language.
Star: A* = {x1x2…xk : k 0 and each xi A} = {ε, good, bad, goodgood,
goodbad, badgood, badbad, goodgoodgood, goodgoodbad, …}.
Attaching any number of strings in A together to get a string in the new language. It is a
unary operation, where ε is always a member of A* (as ‘any number’ also includes 0).
CSC3113: Theory of Computation 17
CLOSURE
A collection of objects is closed under some operation, if applying that
operation to the members of the collection returns an object still in
the collection.
Theorem: The class of regular languages is closed under all three
regular operations (union, concatenation, star), as well as under
complement, intersection, and reverse.
i.e., if set A and B are regular, applying any of these operations on these
sets yields a regular language.
Next, we will prove it for Union operation.
CSC3113: Theory of Computation 18
REGULAR LANGUAGE CLOSED UNDER
UNION
We will prove it by construction.
Let M1 recognize A1, where M1= (Q1, Σ, 1, q1, F1), and
M2 recognize A2, where M2= (Q2, Σ, 2, q2, F2).
Construct M to recognize A1 A2, where M = (Q, Σ, , q0, F).
Q = {(r1, r2) : r1 Q1 and r2 Q2}.
Q = Q1 Q2. (All combination of states of machine M1 and M2).
Σ = Σ1 Σ2.
But here, for simplicity, we have considered Σ1 = Σ2 to be same.
For each (r1,r2) Q and each a Σ, let ((r1,r2), a) = ((r1, a), (r2, a)).
Hence gets a state of M (which actually is a pair of states from M1 and M2), together with an
input symbol, and returns M’s next state.
q0 is the pair (q1, q2).
F = { (r1, r2) : r1 F1 or r2 F2 }
F = (F1 Q2) (Q1 F2)
CSC3113: Theory of Computation 19
DFA UNION EXAMPLE
Let, M= (Q, Σ, , q0, F), where –
M = (Q , Σ, , q , F ),
1 1 1 1 1 Q = {(r1, r2) : r1 Q1 and r2 Q2} = Q1 × Q2
where –
Q1 = {a0,a1,a2}, Q = {(a0,b0), (a0, b1),(a1, b0), (a1, b1),(a2, b0), (a2, b1)},
Σ = {0, 1, 2} Σ = Σ1 Σ2 = {0, 1, 2}
q1 = a0, q0 = (q1,q2) = (a0, b0)
F1 = {a0},
F = { (r1, r2) : r1 F1 or r2 F2 } = (F1 Q2) (Q1 F2)
1 Machine 1
F = {(a0, b0), (a0, b1), (a1, b0), (a2, b0)}
|0 1 | (a
0 0, b0) (a11, b1) (a2, b02) .
2 .
(a0, b0) | (a0(a
, b0,) b )(a1, b1)(a (a ,b )
a0 | a0 0 1 1, 2b0)0 (a2, b1)
a1 a2 (a0, b1) | (a0(a
, b11,) b0)(a1, b0)(a2(a
, 2b, 1b)1) (a0, b0)
a1 | a1 (a1, b0) | (a1(a
, b10,) b1)(a2, b1)(a2(a
, 0b, 0b)0) (a0, b1)
a2 a0 (a1, b1) | (a1(a
, b21,) b0)(a2, b0)(a0(a
, 0b, 1b)1) (a1, b0)
a2| a2 a0
a1 (a2, b0) | (a2(a
, b20,) b1)(a0, b1)(a0(a
, 1b, 0b)0) (a1, b1)
M = (Q , Σ, , q , F ), (a2, b1) | (a2, b1) (a0, b0) (a1, b1)
2 2 2 2 2
where – The above finite automata machine should give the same output for any given
Machine 2
Q = {b ,b input to machine M1 or M2.
2 0 1},
Σ = {0, 1, 2} Here M1 recognizes A1 and M2 recognizes A2. So M should recognize A = A1 A2.
q2 = b0, A1= {w: sum of all the symbols in w is multiple of 3}.
F2 = {b0}, A2 = {w: sum of all the symbols in w is even}.
CSC3113: Theory of Computation 20
2
DFA UNION SIMULATION
2
0
2 (a0,b0) 2
0 (a1,b0) (a2,b0) 0
1 1 1
1
2 (a1,b1)
(a2,b1)
2 2 0
0
1 1
(a0,b1)
Input example: 01120101 0
Input symbol:
Accepted
CSC3113: Theory of Computation 21
CLOSURE UNDER
CONCATENATION
Let M1 recognize A1, where M1= (Q1, Σ, 1, q1, F1), and M2 recognize A2,
where M2= (Q2, Σ, 2, q2, F2).
Construct M to recognize A A , where M = (Q, Σ, , q , F).
1 2 0
M must accept if its input can be broken into two pieces where M1
accepts the first piece and M2 accepts the second piece.
Problem: M doesn’t know where to break its input. i.e., where the
first part ends and the second begins.
To solve the problem we will learn a new technique called
nondeterministic automaton.
CSC3113: Theory of Computation 22
REFERENCES
Elements of the Theory of Computation, Papadimitriou (2nd ed),
DFA + Exercise.
Introduction to Automata Theory, Languages, and Computation
(3rd ed), DFA + Exercise.
CSC3113: Theory of Computation 23
