Report

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |

Theory of Computation

CS3102 – Spring 2014

A tale of computers, math, problem solving, life, love and tragic

death

Nathan Brunelle

Department of

Computer Science

University of Virginia

www.cs.virginia.edu/~njb2b/theory

Midterm

Take home? Vote now.

Date:

1. During the week before Spring break (out March 3, due March 6)?

• Don’t have to worry over the break

2. After Spring break (4 days within March 16-23)?

• 1 more week of content but 2 more weeks to solve problems

• I will hold Skype/Google Hangout office hours over the break

Think about it, vote on Thursday.

Pumping Lemma

Goal: Give a sufficient condition for showing non-regularity

Consider that L is an infinite regular language

Let M be a DFA, L(M)=L

M

Let’s say M has p states

There must be some

String w in L s.t. |w|>p

x2

3

8

1

12

20

By the pigeon-hole principle:

Some state was visited at least twice!

Taking that loop another time must give

another string in the language.

p

Pumping Lemma

If L is a regular language then there is some number p (called

pumping length) where if w is a string in L s.t. |w|>p then w

can be divided into 3 pieces: w=xyz which satisfy:

i

x

1. For each i≥0,xy z L

M

2. |y|>0

y

3. |xy|≤p

3

8

Example:{ a b | n ℕ}

n

p

n

Consider: a p b p

By condition 3 we know: y a

Thus for i=2

we have more a’s than b’s,

so L cannot be regular

1

12

20

z

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Show: { ww

R

|w }

*

p

is not regular

p

Consider ( ab ) ( ba )

By condition 3 we know y (ba ) , this leaves 4 cases:

1. y (ab )

*

b

(ab

)

2. y

Problem: in all of these I only change

the first half!

3. y ( ab ) * a

I needed to “remember” the first half

4. y b ( ab ) a

of the string.

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

n

Show: {a | n is prime }

is not regular

q

Consider

where q is a prime greater than p

m

y may have only a’s, let y= a where m≤p

For i=p+1 we have xy i z a p ( m 1)

Clearly, p(m+1) is not prime

a

7 1

24

For a let y a then y a

7

3

So xyz a 24 a 4 a 28 a 7 ( 3 1)

Pumping Lemma

1. For each i≥0, xy z L

2. |y|>0

3. |xy|≤p

i

Consider: {c a b | i 1 j k }

i

j

k

This language is pumpable but not regular

3 cases:

j k

a

1. If b then let x=ε, y=a

2. If ca j b j then let x=ε, y=c

3. If c i a j b j , i 1 then let x=ε, y=c

Thus every string is pumpable

Nonregular: {c i a j b k | i 1 j k } ca *b * {ca n b n } Then use

pumping Lemma!

Myhill-Nerode Theorem

Gives a necessary and sufficient condition for regularity!

Idea: If two strings terminate in the same state in a DFA then

their membership must be equivalent for any suffix.

w1

If w1 and w 2 meet at

state q then for any string

x , w1 x ends in the same

state as w 2 x

M

q

x

We say w1 and w 2 have

no distinguishing extensions

w2

Myhill-Nerode Theorem

Recall Equivalence Relation:

A relation ~ is called an equivalence relation if:

Reflexive: x ~ x

Symmetric: x ~ y y ~ x

Transitive: x ~ y y ~ z y ~ z

The relation w1 ~ L w 2 if w1 and w 2 have no distinguishing

extensions in language L forms an equivalence relation.

Recall Equivalence Class:

For equivalence relation ~, equivalence class

[ a ] {b | a ~ b }

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ L

Myhill-Nerode Theorem

Myhill Nerode Theorem: L is regular iff * has a finite number

of equivalence classes under relation ~ DE

Given a finite set of equivalence classes, construct a DFA:

Each equivalence class becomes a state:

q 0 [ ]

If character takes a string from equivalence class [ w1 ] to [ w 2 ]

then add a transition from the state for [ w1 ] to the state

for [ w 2 ] .

Accept states are those for equivalence classes of strings in

the language.

Myhill-Nerode Theorem

Extra Credit: Use the Myhill-Nerode Theorem to show the

following languages are non-regular:

{ ww

R

|w }

*

n

{ a | n is prime }

{ a b | n ℕ}

n

n

Language Reversal

Theorem: The regular languages are closed under reversal.

Proof: Construction.

Given a regular language L, show that the language LR { w R | w L}

is also regular.

Let M be a DFA for L, construct M’ to be a NFA for L:

M

M’

ε

q0

ε

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

e.g. if “RingoStarr” is in L, then “Ringo” is in HALF(L)

Let M be a DFA for language L

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”?

M

w

v

Half

Let HALF ( L ) {v | v , w * s.t. | v || w | vw L}

Show that HALF preserves regularity.

Intuition: follow the transitions of M for string v. “Check” that

there is a path from v to an accept state that consumes |v|

characters.

How do we do this “check”? Use the machine for LR

w

M’

Σ

ε

Σ

Σ

Σ

Σ

ε

M

F={(q,q)}

v

Double

Let DOUBLE ( L ) { w | ww L }

Show that DOUBLE preserves regularity.

e.g. if “BamBam” is in L, then “Bam” is in DOUBLE(L)

Let M be a DFA for language L

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

M

M

w

w

“Guess”

Double

Let DOUBLE ( L ) { w | ww L }

Intuition: Run L on w, in parallel non-deterministically “guess”

the end state in machine M on w and check if starting from

that guess puts the machine in an accept state

ε

ε

M

M

M

M1

ε

M2

M

Accept if:

•M ends in state

•M ends in an accept state

F {(

, q ' ) | q ' F }

… |Q |