PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 5:
• Closure Properties
• Regular Expressions
Reading:
Sipser Ch 1.2-1.3
Mark Bun
February 8, 2021
Last Time
• NFAs vs. DFAs
• Subset construction: NFA -> DFA
• Intro to closure properties of regular languages
2/8/2021 CS332 – Theory of Computation 2
Closure Properties
2/8/2021 CS332 – Theory of Computation 3
Operations on languages
Let 𝐴, 𝐵 ⊆ Σ∗ be languages. Define
Union: 𝐴 ∪ 𝐵
Concatenation: 𝐴 ∘ 𝐵 = 𝑎𝑏 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵}
Star: 𝐴∗ = { 𝑎1𝑎2…𝑎𝑛|𝑛 ≥ 0 and 𝑎𝑖 ∈ 𝐴}
Complement: ҧ𝐴
Intersection: 𝐴 ∩ 𝐵
Reverse: 𝐴𝑅 = { 𝑎1𝑎2…𝑎𝑛|𝑎𝑛…𝑎1 ∈ 𝐴}
Theorem: The class of regular languages is closed under all six
of these operations
2/8/2021 CS332 – Theory of Computation 4
{RegularOperations
Proving Closure Properties
2/8/2021 CS332 – Theory of Computation 5
Complement
Complement: ҧ𝐴 = 𝑤 𝑤 ∉ 𝐴}
Theorem: If 𝐴 is regular, then ҧ𝐴 is also regular
Proof idea:
2/8/2021 CS332 – Theory of Computation 6
Complement, Formally
Let 𝑀 = (𝑄, Σ, 𝛿, 𝑞0, 𝐹) be a DFA recognizing a language
𝐴. Which of the following represents a DFA recognizing ҧ𝐴?
a) (𝐹, Σ, 𝛿, 𝑞0, 𝑄)
b) (𝑄, Σ, 𝛿, 𝑞0, 𝑄 ∖ 𝐹), where 𝑄 ∖ 𝐹 is the set of states in
𝑄 that are not in 𝐹
c) (𝑄, Σ, 𝛿′, 𝑞0, 𝐹) where 𝛿′(𝑞, 𝑠) = 𝑝 such that
𝛿(𝑝, 𝑠) = 𝑞
d) None of the above
2/8/2021 CS332 – Theory of Computation 7
Closure under Concatenation
2/8/2021 CS332 – Theory of Computation 8
Concatenation: 𝐴 ∘ 𝐵 = 𝑥𝑦 𝑥 𝐴, 𝑦 𝐵 }
Theorem. If 𝐴 and 𝐵 are regular, 𝐴 ∘ 𝐵 is also regular.
Proof idea: Given DFAs 𝑀𝐴 and 𝑀𝐵, construct NFA by
• Connecting all accept states in 𝑀𝐴 to the start state in 𝑀𝐵.
• Make all states in 𝑀𝐴 non-accepting.
𝐿(𝑀𝐴) = 𝐴 𝐿(𝑀𝐵) = 𝐵
Closure under Concatenation
2/8/2021 CS332 – Theory of Computation 9
Concatenation: 𝐴 ∘ 𝐵 = 𝑥𝑦 𝑥 𝐴, 𝑦 𝐵 }
Theorem. If 𝐴 and 𝐵 are regular, 𝐴 ∘ 𝐵 is also regular.
Proof idea: Given DFAs 𝑀𝐴 and 𝑀𝐵, construct NFA by
• Connecting all accept states in 𝑀𝐴 to the start state in 𝑀𝐵.
• Make all states in 𝑀𝐴 non-accepting.
ε
ε
𝐿(𝑀𝐴) = 𝐴 𝐿(𝑀𝐵) = 𝐵
A Mystery Construction
2/8/2021 CS332 – Theory of Computation 10
ε
ε
𝐿(𝑀𝐴) = 𝐴
𝐿(𝑀𝐵) = 𝐵
Given DFAs 𝑀𝐴 recognizing 𝐴 and 𝑀𝐵 recognizing 𝐵, what does the
following NFA recognize?
Closure under Star
2/8/2021 CS332 – Theory of Computation 11
Star: 𝐴∗ = { 𝑎1𝑎2…𝑎𝑛|𝑛 ≥ 0 and 𝑎𝑖 ∈ 𝐴}
Theorem. If 𝐴 is regular, 𝐴∗ is also regular.
𝐿(𝑀) = 𝐴
Closure under Star
2/8/2021 CS332 – Theory of Computation 12
Star: 𝐴∗ = { 𝑎1𝑎2…𝑎𝑛|𝑛 ≥ 0 and 𝑎𝑖 ∈ 𝐴}
Theorem. If 𝐴 is regular, 𝐴∗ is also regular.
𝐿(𝑀) = 𝐴
ε
ε
ε
On proving your own closure properties
You’ll have homework/test problems of the form “show that
the regular languages are closed under some operation”
What would Sipser do?
– Give the “proof idea”: Explain how to take machine(s)
recognizing regular language(s) and create a new machine
– Explain in a few sentences why the construction works
– Give a formal description of the construction
– No need to formally prove that the construction works
2/8/2021 CS332 – Theory of Computation 13
Regular Expressions
2/8/2021 CS332 – Theory of Computation 14
Regular Expressions
• A different way of describing regular languages
• A regular expression expresses a (possibly complex)
language by combining simple languages using the
regular operations
“Simple” languages: ∅, , {𝑎} for some 𝑎 ∈ Σ
Regular operations:
Union: 𝐴 ∪ 𝐵
Concatenation: 𝐴 ∘ 𝐵 = 𝑎𝑏 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵}
Star: 𝐴∗ = { 𝑎1𝑎2…𝑎𝑛|𝑛 ≥ 0 and 𝑎𝑖 ∈ 𝐴}
2/8/2021 CS332 – Theory of Computation 15
Regular Expressions – Syntax
A regular expression 𝑅 is defined recursively using the
following rules:
1. , ∅, and 𝑎 are regular expressions for every 𝑎 ∈ Σ
2. If 𝑅1 and 𝑅2 are regular expressions, then so are
(𝑅1∪ 𝑅2), (𝑅1∘ 𝑅2), and (𝑅1
∗)
Examples: (over Σ = {𝑎, 𝑏, 𝑐})
𝑎 ∘ 𝑏 ((((𝑎 ∘ (𝑏∗)) ∘ 𝑐) ∪ (((𝑎∗) ∘ 𝑏))∗)) (∅∗)
2/8/2021 CS332 – Theory of Computation 16
Regular Expressions – Semantics
𝐿(𝑅) = the language a regular expression describes
1. 𝐿(∅) = ∅
2. 𝐿 =
3. 𝐿(𝑎) = {𝑎} for every 𝑎 ∈ Σ
4. 𝐿((𝑅1∪ 𝑅2)) = 𝐿(𝑅1) ∪ 𝐿(𝑅2)
5. 𝐿((𝑅1∘ 𝑅2)) = 𝐿(𝑅1) ∘ 𝐿(𝑅2)
6. 𝐿 𝑅1
∗ = (𝐿 𝑅1 )
∗
Example: 𝐿(((𝑎∗) ∘ (𝑏∗))) =
2/8/2021 CS332 – Theory of Computation 17
Simplifying Notation
• Omit ∘ symbol: 𝑎𝑏 = 𝑎 ∘ 𝑏
• Omit many parentheses, since union and concatenation
are associative:
𝑎 ∪ 𝑏 ∪ 𝑐 = 𝑎 ∪ (𝑏 ∪ 𝑐) = (𝑎 ∪ 𝑏) ∪ 𝑐
• Order of operations: Evaluate star, then concatenation,
then union
𝑎𝑏∗ ∪ 𝑐 = (𝑎 𝑏∗ ) ∪ 𝑐
2/8/2021 CS332 – Theory of Computation 18
Examples
Let Σ = {0, 1}
1. 𝑤 𝑤 contains exactly one 1}
2. 𝑤 𝑤 has length at least 3 and its third symbol is 0}
3. 𝑤 every odd position of 𝑤 is 1}
2/8/2021 CS332 – Theory of Computation 19
Syntactic Sugar
• For alphabet Σ, the regex Σ represents 𝐿 Σ = Σ
• For regex 𝑅, the regex 𝑅+ = 𝑅𝑅∗
2/8/2021 CS332 – Theory of Computation 20
Regexes in the Real World
grep = globally search for a regular expression and print
matching lines
Not captured by regular expressions: Backreferences
2/8/2021 CS332 – Theory of Computation 21
Equivalence of Regular
Expressions, NFAs, and DFAs
2/8/2021 CS332 – Theory of Computation 22
Regular Expressions Describe Regular Languages
Theorem: A language 𝐴 is regular if and only if it is
described by a regular expression
Theorem 1: Every regular expression has an equivalent NFA
Theorem 2: Every NFA has an equivalent regular expression
2/8/2021 CS332 – Theory of Computation 23
Regular expression -> NFA
Theorem 1: Every regex has an equivalent NFA
Proof: Induction on size of a regex
Base cases:
𝑅 = ∅
𝑅 =
𝑅 = 𝑎
2/8/2021 CS332 – Theory of Computation 24
Regular expression -> NFA
Theorem 1: Every regex has an equivalent NFA
Proof: Induction on size of a regex
What should the inductive hypothesis be?
a) Suppose some regular expression of length 𝑘 can be
converted to an NFA
b) Suppose every regular expression of length 𝑘 can be
converted to an NFA
c) Suppose every regular expression of length at most 𝑘
can be converted to an NFA
d) None of the above
2/8/2021 CS332 – Theory of Computation 25
Regular expression -> NFA
Theorem 1: Every regex has an equivalent NFA
Proof: Induction on size of a regex
Inductive step:
𝑅 = (𝑅1∪ 𝑅2)
𝑅 = (𝑅1𝑅2)
𝑅 = 𝑅1
∗
2/8/2021 CS332 – Theory of Computation 26
Example
Convert (1(0 ∪ 1))∗ to an NFA
2/8/2021 CS332 – Theory of Computation 27