Mathematics for Information Technology 2
Deterministic Finite Automaton
Saung Hnin Pwint Oo
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
DFA (Deterministic Finite Automaton)
• Deterministic.
• For each state and input symbol, there is exactly one transition to another
state. 𝑀2 = (Q, Σ, 𝛿, 𝑠, 𝐹)
• Finite automaton. 𝑄 = {q1 , q2 , q3 , q4 }
• It has a finite number of states. Σ = {𝑎, 𝑏}
a b
𝛿: 𝑄 × Σ → 𝑄:
𝑞1 a b 𝒒𝟏 𝒒𝟐 𝒒𝟑 𝒒𝟒
𝑞2 𝑞3
𝒂 𝒒𝟐 𝒒𝟐 𝒒𝟒 𝒒𝟒
b a 𝒃 𝒒𝟒 𝒒𝟑 𝒒𝟑 𝒒𝟒
𝑞4
State Diagram of 𝑀2 𝑠 = 𝑞1 ∈ 𝑄
a, b F = 𝑞3 ⊆ 𝑄
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
DFA (Deterministic Finite Automaton)
• When the machine is in a specific state and reads an input
symbol, the next state is always known, predictable,
determinable.
• That is a finite automaton that processes input symbols one
by one.
• If 𝐴 is the set of all strings that machine 𝑀 accepts, 𝐴 is the
language of machine 𝑀.
• 𝐿(𝑀) = 𝐴 means that 𝑀 recognizes 𝐴 or that 𝑀 accepts 𝐴.
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
DFA
a a b
𝑞1 𝑞2 𝑞3 a,b
𝑞0 a b
b b
𝑞5 b 𝑞4
𝑞6 a 𝑞7
b a a
b a
a a b
𝑞1 𝑞2 𝑞3
𝑞0 a b
b b
𝑞5 b 𝑞4
𝑞6
b
2𝑛 2𝑚+1
𝐴= 𝑎 𝑏 𝑛, 𝑚 ≥ 0} R= 𝑎𝑎 ∗ 𝑏𝑏 ∗ 𝑏
Finite automata Computer Engineering Saung Hnin Pwint Oo
01. Exercise
• Define a DFA 𝑀.
• Construct a state diagram of 𝑀 that accepts all binary strings ending with 1.
• Write the language 𝐿 𝑀 that 𝑀 can accept.
• Write Regular Expression 𝑅 that 𝑀 can recognize.
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
02. Exercise
• Define a DFA 𝑀.
• Construct a state diagram of 𝑀 that accepts empty string 𝜀 or all binary strings
ending with 0.
• Write the language 𝐿 𝑀 that 𝑀 can accept.
• Write Regular Expression 𝑅 that 𝑀 can recognize.
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
03. Exercise
• Assume that Σ = {𝑎, 𝑏}. Construct a respective state diagram of 𝐷𝐹𝐴 for each
following language.
a. {𝑤| 𝑤 ℎ𝑎𝑠 𝑎𝑡 𝑙𝑒𝑎𝑠𝑡 𝑡ℎ𝑟𝑒𝑒 𝑎’𝑠 𝑎𝑛𝑑 𝑎𝑡 𝑙𝑒𝑎𝑠𝑡 𝑡𝑤𝑜 𝑏’𝑠}
b. {𝑤| 𝑤 ℎ𝑎𝑠 𝑎𝑛 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑎’𝑠 𝑎𝑛𝑑 𝑒𝑎𝑐ℎ 𝑎 𝑖𝑠 𝑓𝑜𝑙𝑙𝑜𝑤𝑒𝑑 𝑏𝑦 𝑎𝑡 𝑙𝑒𝑎𝑠𝑡 𝑜𝑛𝑒 𝑏}
c. {𝑤| 𝑤 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝑛𝑒𝑖𝑡ℎ𝑒𝑟 𝑡ℎ𝑒 𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑎𝑏 𝑛𝑜𝑟 𝑏𝑎} (Hint: define 𝐿 and 𝐿ത . DFA
for 𝐿: Accept states in 𝐿ത become reject states in 𝐿 and Reject states in 𝐿ത become
accept states in 𝐿.)
d. {𝑤| 𝑤 𝑖𝑠 𝑎𝑛𝑦 𝑠𝑡𝑟𝑖𝑛𝑔 𝑛𝑜𝑡 𝑖𝑛 𝑎𝑏 + ∗ }
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
04. Exercise
• Find all pairs of sets of strings 𝐴 and 𝐵 for which
𝐴𝐵 = {10, 111, 1010, 1000, 10111, 101000}
For example, one possible pair is
𝐴 = {1} and 𝐵 = {0, 11, 010, 000, 0111, 01000}
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
05. Exercise
• Assume that Σ = 0,1 .
• Consider the two languages:
𝐴 = {𝑤| 𝑤 𝑏𝑒𝑔𝑖𝑛𝑠 𝑤𝑖𝑡ℎ 11}
𝐵 = {𝑤 | 𝑤 𝑒𝑛𝑑𝑠 𝑤𝑖𝑡ℎ 00}
• Give a regular expression for the intersection 𝐴 ∩ 𝐵, union 𝐴 ∪ 𝐵, and concatenation
𝐴𝐵 respectively.
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
06. Exercise
• Assume Σ = 0,1 . Find the languages (in Regular Expression) recognized by the
given deterministic finite-state automaton.
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
07. Exercise
• Assume Σ = 0,1 . Find the languages (in Regular Expression) recognized by the
given deterministic finite-state automaton.
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
08. Exercise
• Assume Σ = 0,1 . Find the languages (in Regular Expression) recognized by the
given deterministic finite-state automaton.
Deterministic Finite Automaton Computer Engineering Saung Hnin Pwint Oo
Q/A