Microsoft PowerPoint – CS332-Lec06-ann
BU CS 332 – Theory of Computation
Lecture 6:
• Regexes = NFAs
• Non‐regular languages
Reading:
Sipser Ch 1.3
“Myhill‐Nerode” note
Sipser Ch 1.4 (optional)
Mark Bun
February 10, 2021
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 ) (with simplified notation)
∗ ∗ ∗
2/10/2021 CS332 ‐ Theory of Computation 2
Regular Expressions – Semantics
the language a regular expression describes
1.
2.
3. for every
6. ∗ ∗
Example: ∗ ∗
2/10/2021 CS332 ‐ Theory of Computation 3
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/10/2021 CS332 ‐ Theory of Computation 4
Regular expression ‐> NFA
Theorem 1: Every regex has an equivalent NFA
Proof: Induction on size of a regex
Base cases:
2/10/2021 CS332 ‐ Theory of Computation 5
Regular expression ‐> NFA
Theorem 1: Every regex has an equivalent NFA
Proof: Induction on size of a regex
Inductive step:
∗
2/10/2021 CS332 ‐ Theory of Computation 6
Example Convert ∗ to an NFA
2/10/2021 CS332 ‐ Theory of Computation 7
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/10/2021 CS332 ‐ Theory of Computation 8
NFA ‐> Regular expression
Theorem 2: Every NFA has an equivalent regex
Proof idea: Simplify NFA by “ripping out” states one at a
time and replacing with regexes
2/10/2021 CS332 ‐ Theory of Computation 9
0
1
001*0
Generalized NFAs
• Every transition is labeled by a regex
• One start state with only outgoing transitions
• Only one accept state with only incoming transitions
• Start state and accept state are distinct
2/10/2021 CS332 ‐ Theory of Computation 10
∗
𝑠 𝑎
Generalized NFA Example
2/10/2021 CS332 ‐ Theory of Computation 11
𝑠
𝑎
∗
𝑠 𝑎
Which of these strings is accepted?
Which of the following strings is accepted by this GNFA?
2/10/2021 CS332 ‐ Theory of Computation 12
a) 𝑎𝑎𝑎
b) 𝑎𝑎𝑏𝑏
c) 𝑏𝑏𝑏
d) 𝑏𝑏𝑎
∗
𝑠 𝑎
NFA ‐> Regular expression
2/10/2021 CS332 ‐ Theory of Computation 13
NFA GNFA
GNFA
GNFA
Regex
𝑘 states
𝑘 2 states
𝑘 1 states
2 states
…
NFA ‐> GNFA
2/10/2021 CS332 ‐ Theory of Computation 14
NFAε
ε
ε
ε
• Add a new start state with no incoming arrows.
• Make a unique accept state with no outgoing arrows.
GNFA ‐> Regular expression
Idea: While the machine has more than 2 states, rip one
out and relabel the arrows with regexes to account for the
missing state
2/10/2021 CS332 ‐ Theory of Computation 15
∗
1 32
1 3
GNFA ‐> Regular expression
Idea: While the machine has more than 2 states, rip one
out and relabel the arrows with regexes to account for the
missing state
2/10/2021 CS332 ‐ Theory of Computation 16
∗
1 32
1 3
GNFA ‐> Regular expression
Idea: While the machine has more than 2 states, rip one
out and relabel the arrows with regexes to account for the
missing state
2/10/2021 CS332 ‐ Theory of Computation 17
∗
1 32
1 3
GNFA ‐> Regular expression
Idea: While the machine has more than 2 states, rip one
out and relabel the arrows with regexes to account for the
missing state
2/10/2021 CS332 ‐ Theory of Computation 18
1 32
1
2
3
4
1 3
2/10/2021 CS332 ‐ Theory of Computation 19
Non‐Regular Languages
2/10/2021 CS332 ‐ Theory of Computation 20
Motivating Questions
• We’ve seen techniques for showing that languages are
regular
• How can we tell if we’ve found the smallest DFA
recognizing a language?
• Are all languages regular? How can we prove that a
language is not regular?
2/10/2021 CS332 ‐ Theory of Computation 21
An Example
∗
Claim: Every DFA recognizing needs at least 3 states
Proof: Let be any DFA recognizing . Consider running
on each of
2/10/2021 CS332 ‐ Theory of Computation 22
A General Technique
Definition: Strings and are distinguishable by if
there exists such that exactly one of or is in .
Ex.
Definition: A set of strings is pairwise distinguishable by
if every pair of distinct strings is distinguishable
by .
Ex.
2/10/2021 CS332 ‐ Theory of Computation 23
𝐴 𝑤 ∈ 0, 1 ∗ 𝑤 ends with 01
A General Technique
Theorem: If is pairwise distinguishable by , then every
DFA recognizing needs at least states
Proof: Let be a DFA with states. By the
pigeonhole principle, there are such that ends
up in same state on and
2/10/2021 CS332 ‐ Theory of Computation 24
Back to Our Example
∗
Theorem: If is pairwise distinguishable by , then every
DFA recognizing needs at least states
2/10/2021 CS332 ‐ Theory of Computation 25