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