CS代考计算机代写 BU CS 332 – Theory of Computation

BU CS 332 – Theory of Computation
Lecture 5:
• More on pumping
• Regular expressions
• Regular expressions = regular languages
Mark Bun February 5, 2020
Reading: Sipser Ch 1.3

More on Pumping
2/5/2020 CS332 – Theory of Computation 2

Pumping Lemma (Formal)
Let 𝐿 be a regular language.
Then there exists a “pumping length” 𝑝 such that
For every 𝑤 ∈ 𝐿 where |𝑤| ≥ 𝑝,
𝑤 can be split into three parts 𝑤 = 𝑥𝑦𝑧 where:
1. |𝑦| > 0
2. |𝑥𝑦| ≤ 𝑝
3. 𝑥𝑦𝑖𝑧𝐿forall𝑖 ≥ 0
2/5/2020 CS332 – Theory of Computation 3

General Strategy for proving 𝐿 is not regular Proof by contradiction: assume 𝐿 is regular.
Then there is a pumping length 𝑝.
1.Find𝑤∈𝐿with 𝑤 ≥𝑝
2. Show that 𝑤 cannot be pumped
3. Conclude 𝐿 must not have been regular
2/5/2020 CS332 – Theory of Computation 4

Pumping down
Claim:𝐿= 0𝑖1𝑗 𝑖>𝑗≥0}isnotregular
Proof: Assume 𝐿 is regular with pumping length 𝑝
1.Find𝑤∈𝐿with 𝑤 ≥𝑝
2. Show that 𝑤 cannot be pumped
Formally If 𝑤 = 𝑥𝑦𝑧 with |𝑥𝑦| ≤ 𝑝, then…
2/5/2020 CS332 – Theory of Computation 5

Reusing a Proof
Pumping a language can be lots of work… Let’s try to reuse that work!
How might we show that
𝐵𝐴𝐿𝐴𝑁𝐶𝐸𝐷 = 𝑤 𝑤 has an equal # of 0s and 1s}
is not regular?
0𝑛1𝑛 𝑛 ≥ 0} = 𝐵𝐴𝐿𝐴𝑁𝐶𝐸𝐷 ∩ 𝑤 all 0s in 𝑤 appear before all 1s}
2/5/2020 CS332 – Theory of Computation 6

Using Closure Properties
If 𝐴 is not regular, we can show a related language 𝐵 is not regular
𝐵∩𝐶= (regular)
𝐴
(not regular) any of {∘, ∪, ∩} or, for one language, {¬, R, *}
By contradiction: If 𝐵 is regular, then 𝐵 ∩ 𝐶 (= 𝐴) is regular.
But 𝐴 is not regular so neither is 𝐵! 2/5/2020 CS332 – Theory of Computation 7

Example
Prove 𝐵 = {0𝑖1𝑗|𝑖 ≠ 𝑗} is not regular
using nonregular language 𝐴 = 0𝑛1𝑛 𝑛 ≥ 0
and regular language
𝐶 = 𝑤 all 0s in 𝑤 appear before all 1s}
2/5/2020
CS332 – Theory of Computation 8

Regular Expressions
2/5/2020 CS332 – Theory of Computation 9

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…𝑎𝑛|𝑛 ≥0and𝑎𝑖 ∈𝐴}
2/5/2020 CS332 – Theory of Computation 10

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
12
(𝑅 ∪ 𝑅 ), (𝑅 ∘ 𝑅 ), and (𝑅∗) 12121
Examples: (over Σ = {𝑎, 𝑏, 𝑐})
𝑎 ∘ 𝑏 ((((𝑎 ∘ (𝑏∗)) ∘ 𝑐) ∪ (((𝑎∗) ∘ 𝑏))∗)) (∅∗)
2/5/2020 CS332 – Theory of Computation 11

Regular Expressions – Semantics
𝐿(𝑅) = the language a regular expression describes
1. 𝐿(∅)=∅
2. 𝐿 𝜀 = 𝜀
3. 𝐿(𝑎) = {𝑎}forevery𝑎∈Σ
4. 𝐿((𝑅 ∪𝑅 ))=𝐿(𝑅 )∪𝐿(𝑅 ) 1212
5. 𝐿((𝑅 ∘𝑅 ))=𝐿(𝑅 )∘𝐿(𝑅 ) 1212
6.𝐿𝑅∗ =(𝐿𝑅)∗ 11
Example: 𝐿(((𝑎∗) ∘ (𝑏∗))) =
2/5/2020 CS332 – Theory of Computation 12

Simplifying Notation
• Omit∘symbol: 𝑎𝑏 = 𝑎∘𝑏
• Omit many parentheses, since union and concatenation
are associative:
𝑎∪𝑏∪𝑐 = 𝑎∪(𝑏∪𝑐) = (𝑎∪𝑏)∪𝑐
• Order of operations: Evaluate star, then concatenation, then union
𝑎𝑏∗ ∪ 𝑐 = (𝑎 𝑏∗ ) ∪ 𝑐
2/5/2020 CS332 – Theory of Computation 13

Examples
Let Σ = {0,1}
1.
𝑤 𝑤 contains exactly one 1}
2.
𝑤 𝑤 has length at least 3 and its third symbol is 0}
𝑤 everyoddpositionof𝑤is1}
2/5/2020 CS332 – Theory of Computation 14
3.

Syntactic Sugar
• For alphabet Σ, the regex Σ represents 𝐿(Σ) = Σ • For regex 𝑅, the regex 𝑅+ = 𝑅𝑅∗
Not captured by regular expressions: Backreferences
2/5/2020 CS332 – Theory of Computation 15

Equivalence of Regular Expressions, NFAs, and DFAs
2/5/2020 CS332 – Theory of Computation 16

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/5/2020 CS332 – Theory of Computation 17

Regular expression -> NFA
Theorem 1: Every regex has an equivalent NFA Proof: Induction on size of a regex
Base cases:
𝑅=∅ 𝑅=𝜀 𝑅=𝑎
2/5/2020 CS332 – Theory of Computation 18

Regular expression -> NFA
Theorem 1: Every regex has an equivalent NFA Proof: Induction on size of a regex
Inductive step:
𝑅 = (𝑅 ∪ 𝑅 ) 12
𝑅 = (𝑅 𝑅 ) 12
𝑅 = 𝑅∗ 1
2/5/2020
CS332 – Theory of Computation 19

Example
Convert (1(0 ∪ 1))∗ to an NFA
2/5/2020 CS332 – Theory of Computation 20

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
0 01*0 0
1
2/5/2020 CS332 – Theory of Computation 21

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/5/2020 CS332 – Theory of Computation 22

Generalized NFA Example
𝑎∪𝑏
𝑎∗𝑏 𝑞𝑠
𝑞 𝑎 𝑞𝑎 𝑅(𝑞𝑠,𝑞) =
𝑅(𝑞𝑎,𝑞) = 𝑅(𝑞,𝑞𝑠) =
2/5/2020
CS332 – Theory of Computation 23

NFA -> Regular expression
NFA
GNFA
𝑘 states
𝑘 + 2 states
𝑘 + 1 states
GNFA
GNFA
2 states
2/5/2020 CS332 – Theory of Computation
24
Regex
…

NFA -> GNFA
NFA
ε
ε
ε
ε
• Add a new start state with no incoming arrows.
• Make a unique accept state with no outgoing arrows.
2/5/2020 CS332 – Theory of Computation 25

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
𝑎∗𝑏 𝑞1
𝑞𝑎𝑞 23
𝑞1
𝑞3
2/5/2020
CS332 – Theory of Computation
26

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
𝑎∪𝑏
𝑞𝑎𝑞 23
𝑎∗𝑏 𝑞1
𝑞1
𝑞3
2/5/2020
CS332 – Theory of Computation
27

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
𝑎∪𝑏
𝑞𝑎𝑞 23
𝑏
𝑎∗𝑏 𝑞1
𝑞1
𝑞3
2/5/2020
CS332 – Theory of Computation
28

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
𝑞 𝑅3 𝑞
𝑅4
𝑅1
𝑞1
23
𝑞1
𝑞3
2/5/2020
CS332 – Theory of Computation
29

Example
𝑎 𝑎
1
2
𝑎
3
𝑏 𝑏
2/5/2020
CS332 – Theory of Computation 30

2/5/2020 CS332 – Theory of Computation 31

2/5/2020 CS332 – Theory of Computation 32

2/5/2020 CS332 – Theory of Computation 33

2/5/2020 CS332 – Theory of Computation 34