### 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.

Slide 1

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 |

Slide 2

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 |

Slide 3

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 |

Slide 4

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 |

Slide 5

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 |

Slide 6

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 |

Slide 7

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 |

Slide 8

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 |

Slide 9

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 |

Slide 10

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 |

Slide 11

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 |

Slide 12

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 |

Slide 13

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 |

Slide 14

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 |

Slide 15

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 |

Slide 16

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 |