Microsoft PowerPoint – CS332-Lec05-ann
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: ∗ … | and
Complement:
Intersection:
Reverse: … | …
Theorem: The class of regular languages is closed under all six
of these operations
2/8/2021 CS332 ‐ Theory of Computation 4
Regular
Operations
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 be a DFA recognizing a language
. Which of the following represents a DFA recognizing ?
a)
b) , where is the set of states in
that are not in
c) 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: ∗ … | and
Theorem. If 𝐴 is regular, 𝐴∗ is also regular.
Closure under Star
2/8/2021 CS332 ‐ Theory of Computation 12
Star: ∗ … | 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: ∗ … | 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 and are regular expressions, then so are
, , and ∗
Examples: (over )
∗ ∗ ∗ ∗
2/8/2021 CS332 ‐ Theory of Computation 16
Regular Expressions – Semantics
the language a regular expression describes
1.
2.
3. for every
6. ∗ ∗
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
1. contains exactly one
2. has length at least 3 and its third symbol is
3. every odd position of is
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:
∗
2/8/2021 CS332 ‐ Theory of Computation 26
Example
Convert ∗ to an NFA
2/8/2021 CS332 ‐ Theory of Computation 27
2/8/2021 CS332 ‐ Theory of Computation 28