EECS2001:
Introduction to Theory of Computation
Summer 2019
Ali Mahmoodi
amahmoodi@cse.yorku.ca
Office: Lassonde 2015 Course page: Moodle
Notes based on work by Professor Suprakash Datta
5/23/2019 EECS2001, Summer 2019 1
Expressive power NFA & DFA
• Are there languages recognized by DFA but not NFA?
• Are there languages recognized NFA but not by DFA?
• It turns out the NFA and DFA recognize the same class of languages.
• This is both surprising and useful.
• It is useful since describing an NFA for a language is often easier than DFA,
5/23/2019 EECS2001, Summer 2019 2
Equivalence of NFA, DFA
• Pages 54-58 (Sipser, 2nd ed)
• We will prove that every NFA is equivalent to a DFA (with upto exponentially more states).
• Non-determinism does not help FA’s to recognize more languages!
5/23/2019 EECS2001, Summer 2019 3
Terminology: closure
• A set is defined to be closed under an operation if that operation on members of the set always produces a member of the same set. (adapted from wikipedia)
E.g.:
• The integers are closed under addition, multiplication.
• The integers are not closed under division
• Σ* is closed under concatenation
• A set can be defined by closure — Σ* is called the (Kleene) closure of Σ under concatenation.
5/23/2019 EECS2001, Summer 2019 4
Epsilon Closure
• Let N=(Q,,,q0,F) be any NFA
• Consider any set R Q
• E(R) = {q | q can be reached from a state in R by following 0 or more - transitions}
• E(R) is the epsilon closure of R under - transitions
5/23/2019 EECS2001, Summer 2019 5
Example
• E({1}) is the set of states reachable from {1} by travelling along ε arrows:
• E({1}) = {1, 3}
5/23/2019 EECS2001, Summer 2019 6
Proving equivalence
For all languages L *
L = L(N) iff for some
NFA N
One direction is easy:
A DFA M is also a NFA N. So N does not have to be `constructed’ from M
5/23/2019 EECS2001, Summer 2019 7
L = L(M) for some
DFA M
Proving equivalence – contd. The other direction:
Construct M from N
• N = (Q,,,q0,F)
• Construct M= (Q’,,’,q’0,F’) such that,
5/23/2019
EECS2001, Summer 2019 8
– –
for any string w *,
w is accepted by N iff w is accepted by M
Assume no Ɛ moves
• Assume that is not used in the NFA N: – If N has k states, M needs to remember
2k states: keep track of each subset of Q
– So Q’ = P (Q), q’0 = {q0}
-For𝑅∈𝑄′𝑎𝑛𝑑𝑎∈Σ𝑙𝑒𝑡𝛿′ 𝑅,𝑎 =ሼ𝑞∈ 𝑄ȁ𝑞∈𝛿 𝑟,𝑎 𝑓𝑜𝑟𝑠𝑜𝑚𝑒𝑟 ∈𝑅}
’(R,a) = ((r,a)) over all r R, R Q’ – F’ = {R Q’| R contains an accept state of N}
5/23/2019 EECS2001, Summer 2019 9
With Ɛ moves
1. Q’=P(Q)
2. q’0 = E({q0})
3. for all R Q’ and a Σ
’(R, a) = {q Q | q E((r,a)) for some rR}
4. F’= { R Q’| R contains an accept state of N}
5/23/2019 EECS2001, Summer 2019 10
Why the construction works
• for any string w *,
• w is accepted by N iff w is accepted by
M
• Can prove using induction on the number of steps of computation…
5/23/2019 EECS2001, Summer 2019 11
Example 1.41
• Construct a DFA D for the following NFA N4
Q’ =
ሼ∅, 1, 2, 3, 1,2, 1,3, 2,3, 1,2,3}
𝐹′=ሼ1, 1,2, 1,3, 1,2,3}
5/23/2019 EECS2001, Summer 2019 12
Example 1.41 Continued
Q’ =
ሼ∅, 1, 2, 3, 1,2, 1,3, 2,3, 1,2,3} 𝐹′=ሼ1, 1,2, 1,3, 1,2,3}
R Q’ and a Σ
’(R, a) = {q Q | q E((r,a)) for some rR}
𝛿′ 1,𝑎=∅,𝑠𝑖𝑛𝑐𝑒𝐸𝛿1,𝑎 =𝐸∅=∅
𝛿′ 1,3,𝑎=1,3𝑠𝑖𝑛𝑐𝑒𝐸𝛿3,𝑎 =𝐸1 =1,3
𝛿′ 1,3,𝑏=2
𝛿′ 2,𝑎=2,3
𝛿′ 2,3,𝑎 =ሼ1,2,3}
5/23/2019 EECS2001, Summer 2019 13
Example 1.41 Continued
The DFA D obtained from NFA N4
5/23/2019 EECS2001, Summer 2019 14
Simplify the Machine
• Some states cannot be reached
5/23/2019 EECS2001, Summer 2019 15
Recall: Regular Languages
The language recognized by a finite automaton M is denoted by L(M).
A regular language is a language for which there exists a recognizing finite automaton.
5/23/2019 EECS2001, Summer 2019 16
Terminology: Regular Operations
Pages 44-47 (Sipser)
The regular operations are: 1. Union
2. Concatenation
3. Star (Kleene Closure): For a language A,
A* = {w1w2w3…wk| k 0, and each wi A}
5/23/2019 EECS2001, Summer 2019 17
Closure Properties
• Set of regular languages is closed under
— Complementation
– Union
– Concatenation
– Star (Kleene Closure)
5/23/2019 EECS2001, Summer 2019 18
Complement of a regular language
• Swap the accepting and non-accept states of M to get M’.
• The complement of a regular language is regular.
5/23/2019 EECS2001, Summer 2019 19
Other closure properties
Union: Can be done with DFA, but using a complicated construction.
Concatenation: We tried and failed Star: ???
We introduced non-determinism in FA
5/23/2019 EECS2001, Summer 2019 20
Recall: NFA drawing conventions
• Not all transitions are labeled
• Unlabeled transitions are assumed to go to a reject state from which the automaton cannot escape
5/23/2019 EECS2001, Summer 2019 21
Closure under regular operations
Union (new proof):
5/23/2019 EECS2001, Summer 2019 22
Closure under regular operations
Concatenation:
5/23/2019 EECS2001, Summer 2019 23
Closure under regular operations
Star:
5/23/2019 EECS2001, Summer 2019 24
Incorrect reasoning about RL
• Since L1 = {w| w=an, n N},
L2 = {w| w = bn, n N} are regular,
therefore L1 • L2 = {w| w=an bn, n N} is regular
• If L1 is a regular language, then L2 = {wR| w L1} is regular, and
Therefore L1 • L2 = {w wR | w L1} is regular
5/23/2019 EECS2001, Summer 2019
25
Characterizing FA languages
• Regular expressions
• We are familiar with arithmetic expressions using arithmetic operations
(5+3)×4
• Similarly use regular operations to build expression describing languages (called regular expressions) ∗
0∪1 0
5/23/2019 EECS2001, Summer 2019 26
Regular Expressions
• Regular expressions provide a method for describing patterns
• In text applications allow to search for strings satisfying a pattern
• Unix ‘grep’ and ‘AWK’ commands use them
• Important in computer science apps
• Lexical Analyzer Generators (part of compilers)
5/23/2019 EECS2001, Summer 2019 27
Regular Expressions (Def. 1.52)
Given an alphabet , R is a regular expression if: (INDUCTIVE DEFINITION)
• R = a, with a
• R =
• R=
• R = (R1R2), with R1 and R2 regular expressions
• R = (R1•R2), with R1 and R2 regular expressions
• R = (R1*), with R1 a regular expression
Precedence order: *, •,
5/23/2019 EECS2001, Summer 2019 28
Regular Expressions (Cont)
• Note that regular expressions ε and a represent languages {Ɛ} and {a}
• Regular expression ∅ represents the empty language
• ∪,∗,∙ represent the languages obtained by taking the union, star, or concatenation
5/23/2019 EECS2001, Summer 2019 29
• e1
• e2
• e3
• e4
• e5
• e6
Examples
= a b,
= ab ba,
= a*,
= (a b)*,
= (em . en),
= a*b a*bb,
L(e1) = {a,b}
L(e2) = {ab,ba} L(e3) = {a}*
L(e4) = {a,b}*
L(e5) = L(em) • L(en)
L(e6) = {w| w {a,b}* and w has 0 or more a’s followed by 1 or 2 b’s}
5/23/2019 EECS2001, Summer 2019 30
More definition/example
• 𝑅+ = 𝑅𝑅∗ (Note that R* contains zero or more concatenation of strings in R, while R+ oneormore,𝑅+ ∪ 𝜀 =𝑅^∗)
• Use R and L(R) to distinguish between RE and the language it describes
• Testing your understanding
5/23/2019
EECS2001, Summer 2019 31
–𝑅∪∅=? – 𝑅 ∙ 𝜀 =? –𝑅∪𝜀=?
–𝑅∙∅=?
=R
= R
Not necessarily R, e.g. R = 0 Not necessarily R, e.g. R= 0
RE uses in Compilers
• Numerical constants that may include fractional parts can be described by
+∪−∪𝜀 (𝐷+ ∪𝐷+.𝐷∗ ∪𝐷∗.𝐷+)
• Where D={0, 1, …, 9}
• Examples +5, 16, +88.91, -.01
5/23/2019 EECS2001, Summer 2019 32
Example 1.53
•Σ= 0,1
5/23/2019 EECS2001, Summer 2019 33