# 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