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

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

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 where:
For every where , can be split into three parts
1.
2.
3. 𝑖  for all
2/5/2020
CS332 ‐ Theory of Computation
3

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

Pumping down
Claim: 􏶞 􏶢 Proof: Assume
is not regular
is regular with pumping length
1. Find
with
cannot be pumped
2. Show that 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
= hasanequal#of sand s
is not regular?
0𝑛1𝑛 𝑛􏶖 0􏶤=𝐵𝐴𝐿𝐴𝑁𝐶𝐸𝐷∩ 𝑤 all0sin𝑤appearbeforeall1s􏶤
2/5/2020 CS332 ‐ Theory of Computation 6

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

Example
Prove 􏶞 􏶢 is not regular
using nonregular language and regular language
􏵳􏵳
2/5/2020
CS332 ‐ Theory of Computation
8
all s in appear before all
s

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: ∗ 􏵶 􏶊… 􏵳|
and 􏶞
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
􏵶 􏶊, 􏵶 􏶊,and 􏵶∗
Examples: (over ∗ ) ∗ ∗ ∗
2/5/2020 CS332 ‐ Theory of Computation
11

Regular Expressions – Semantics
1. 2. 3.
for every
6.
􏵶∗ 􏵶∗
Example:
∗∗
the language a regular expression describes
􏵶􏶊􏵶􏶊 􏵶􏶊􏵶􏶊
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
1.
contains exactly one
2.
has length at least 3 and its third symbol is
3.
every odd position of is
2/5/2020
CS332 ‐ Theory of Computation 14

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:
2/5/2020
CS332 ‐ Theory of Computation 19
􏵶􏶊 􏵶􏶊
􏵶∗

Example
Convert ∗ to an NFA
2/5/2020 CS332 ‐ Theory of Computation 20

Example
2/5/2020 CS332 ‐ Theory of Computation 21