[PDF] CS411-2015S-07 Non-Regular Languages Closure Properties of PDF lecture7.printable.pdf

Closure Properties of Regular Languages DFA State Is LREG closed under union? E(0)[i, j]=1 if qi and qj are both accept states, or both non-accept states

(a) Union of two non-regular languages cannot be regular Now L1 is regular (since regular languages are closed under complementation) Since, L1 is regular, hence its intersection with L i e L1 ∩ L = L2 is regular (since regular languages are closed under intersection) Therefore, L2 is regular

[PDF] CS660 Homework 2 - Department of Computer Science at the

Are there two non-regular languages whose concatenation is regular? Show that the intersection of two sets of languages can be empty, finite (of arbitrarily

[PDF] Regular and Nonregular Languages

Closure Properties of Regular Languages ○ Union ○ Concatenation ○ Kleene star which is non-prime if both factors are greater than 1: (x + z) > 1

[PDF] CS411-2015S-07 Non-Regular Languages Closure Properties of

Closure Properties of Regular Languages DFA State Is LREG closed under union? E(0)[i, j]=1 if qi and qj are both accept states, or both non-accept states

[PDF] Regular and Non regular Languages - TechJourneyin

nonempty alphabet So there are many more nonregular languages than there are reg- ular ones EXAMPLE 8 1 The Intersection of Two Infinite Languages

[PDF] Non-regular languages and the pumping lemma - MIT

cardinality, there must be some non-regular languages By the Pigeonhole Principle, two pigeons share a hole, languages is closed under intersection

[PDF] Regular and Nonregular Languages

Regular and Non-Regular Languages Are all finite Are all infinite languages non-regular? The two most useful ones are closure under: • Intersection

[PDF] Chapter Three: Closure Properties for Regular Languages

Once we have defined languages formally, we can consider For example, is the intersection of two regular languages be non-accepting, and make the non-

[PDF] linz_ch4pdf

regular languages, but are not as easy for other language families 99 construction for the intersection of two regular languages given in Theorem 4 1, finding

[PDF] union security insurance company medicare supplement claims mailing address

[PDF] uniontown pa warrant list 2020

[PDF] unique businesses in switzerland

[PDF] unique characteristics of ants

[PDF] unique college essays

[PDF] unique practices in singapore

[PDF] unisex joggers size chart

[PDF] unisex size chart

[PDF] unit 12 trigonometry homework 6 law of cosines answers

[PDF] unit 3: weather lesson 49 worksheet answers

[PDF] unit 6: prepositions

[PDF] unit a1 lecturers close bolton

[PDF] unit of magnetic flux

[PDF] unit of magnetization

[PDF] unit test arraylist java

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization1

07-0:Fun with Finite Automata

Create a Finite Automata (DFA or NFA) for the language:

L={0n1n:n >0}

{01, 0011, 000111, 00001111, ...}

07-1:Fun with Finite Automata

L={0n1n:n >0}is not regular!

Why?

Need to keep track of how many 0"s there are, and match 1"s Only way to store information in DFA is through what state themachine is in

Finite number of states (DFA)

Unbounded number of 0"s before the 1"s

07-2:Non-Regular Languages

If a DFAMhaskstates, and a stringwaccepted byMhasncharacters,n > k, computation must include a loop

Pigeonhole Principle:

More transitions than states

Some transition must enter the same state twice

07-3:Non-Regular Languages

xz y

Break string intow=xyz

Ifw=xyzis accepted, thenw?=xyyzwill also be accepted Ifw=xyzis accepted, thenw?=xyyyzwill also be accepted Ifw=xyzis accepted, thenw?=xzwill also be accepted

07-4:Pumping Lemma

If a languageLis regular, then:

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization2

?n≥1such that any stringw?Lwith|w| ≥ncan be rewritten asw=xyzsuch that

y?=?

|xy|< n

xyiz?Lfor alli≥0

07-5:Using the Pumping Lemma

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

Show that foreverylegal decomposition ofw=xyzsuch that:

|xy|< n

y?=?

There is anisuch thatxyiz??L

Conclude thatLmust not be regular

07-6:Using the Pumping Lemma

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

Show that foreverylegal decomposition ofw=xyzsuch that:

|xy|< n

y?=?

There is anisuch thatxyiz??L

Conclude thatLmust not be regular

L={0n1n:n >0}

07-7:Using the Pumping Lemma

L={0n1n:n >0}

Letnbe the constant of the pumping lemma

Consider the stringw= 0n1n

If we breakw=xyzsuch that|xy|< n,|y|>0,

thenxandymust be all 0"s

x= 0j,y= 0k,z= 0n-k-j1n

Considerw?=xy2z= 0n+k1nfor some0< k < n

w???L

Lis not regular (by the pumping lemma)

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization3

07-8:Using the Pumping Lemma

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

Show that foreverylegal decomposition ofw=xyzsuch that:

|xy|< n

y?=?

There is anisuch thatxyiz??L

Conclude thatLmust not be regular

L={ww:w?(a+b)?}07-9:Using the Pumping Lemma

L={ww:w?(a+b)?}

Letnbe the constant of the pumping lemma

Considerw=anbanb?L

If we breakw=xyzsuch that|xy|< n,|y|>0,

thenxandymust be alla"s

x=aj,y=ak,z=an-k-jban

Considerw?=xy2z=an+kbanb. As long ask >0, the first half ofw?contains alla"s, while the second half

contains twob"s. Thusw?is not of the formww, and is not inL. Hence,Lis not regularby the pumpinglemma.

07-10:Using the Pumping LemmaYou have an adversary who thinksLis regular. You need to prove that your adversary is wrong.

you LanguageLis not regular! adv Yes it is! I have a DFA to prove it! you Oh really? How many states are in your DFA? advn

you OK, here"s a stringw?Lwith|w|> n. Your machine must acceptw- but since|w|> n, there must be a loop in your computation. Where"s the loop?

adv Right here! (breakswintoxyz, whereyis the part of the string that goes throughthe loop)

you Ah hah! If we go through the loop 2 times instead of 1, we geta string not inLthat your machine will accept!

adv Drat!

07-11:Using the Pumping Lemma

You have an adversary who thinksLis regular. You need to prove that your adversary is wrong.

Your adversary picks ann

You pick aw?L(such that|w|> n)

Your adversary breakswintoxyz(subject to|xy|< n,|y|>0)

You pick anisuch thatxyiz??L

07-12:Using the Pumping Lemma

You have an adversary who thinksLis regular. You need to prove that your adversary is wrong.

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization4

Your adversary picks ann

You pick aw?L(such that|w|> n)

Your adversary breakswintoxyz(subject to|xy|< n,|y|>0)

You pick anisuch thatxyiz??L

You don"treallyhave an adversary, so you need to show that foranyn, you can create a stringw, and foranyway

thatwcan be broken intoxyz, there is anisuch thatxyiz??L

07-13:Using the Pumping Lemma

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

Show that foreverylegal decomposition ofw=xyzsuch that:

|xy|< n

y?=?

There is anisuch thatxyiz??L

Conclude thatLmust not be regular

L={w:w?(a?b?)?wcontains morea"s thanb"s}

07-14:Using the Pumping Lemma

L={w:w?(a?b?)?wcontains morea"s thanb"s}

Letnbe the constant of the pumping lemma

Considerw=anbn-1?L

If we breakw=xyzsuch that|xy|< n,|y|>0,

thenxandymust be alla"s

x=aj,y=ak,z=an-k-jbn-1

Considerw?=xy0z=an-kbn-1. As long ask >0,w?has at least as manyb"s asa"s, and is not inL. Hence,

Lis not regular, by the pumping lemma.

07-15:Using the Pumping Lemma

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

Show that foreverylegal decomposition ofw=xyzsuch that:

|xy|< n

y?=?

There is anisuch thatxyiz??L

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization5

Conclude thatLmust not be regular

L={w:w?(a+b)??whas an even number ofa"s and an odd number ofb"s}

07-16:Using the Pumping Lemma

L={w:w?(a+b)??whas an even number ofa"s and an odd number ofb"s}

Letnbe the constant of the pumping lemma

Considerw=a2nb?L

If we breakw=xyzsuch that|xy|< n,|y|>0,

thenxandymust be alla"s

x=aj,y=ak,z=a2n-k-jb

As long as k is even,w?=xyiz?Lfor alli

Remember, we don"t get to choose how the string is broken intoxyz- need to show that foranyway the string can be broken

intoxyz, there exists anisuch thatxyiz??L

07-17:Using the Pumping Lemma

L={w:w?(a+b)??whas an even number ofa"s and an odd number ofb"s} We failed to proveLis not regular. Does that mean thatLmust be regular?

07-18:Using the Pumping Lemma

L={w:w?(a+b)??whas an even number ofa"s and an odd number ofb"s} We failed to proveLis not regular. Does that mean thatLmust be regular?

No! We may not have chosen a clever enoughw

Similarly, failing to create an NFA for a language does not prove that it is not regular.

How can we prove thatLis regular?

07-19:Using the Pumping Lemma

L={w:w?(a+b)??whas an even number ofa"s and an odd number ofb"s} We failed to proveLis not regular. Does that mean thatLmust be regular?

No! We may not have chosen a clever enoughw

Similarly, failing to create an NFA for a language does not prove that it is not regular.

How can we prove thatLis regular?

Create a regular expression, DFA, or NFA that describesL

07-20:Closure Properties

Since some languages are regular, and some are not, we can consider closure properties of regular languages

IsLREGclosed under union?

IsLREGclosed under complementation?

IsLREGclosed under intersection?

07-21:Closure Properties

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization6

IsLREGclosed under union?

07-22:Closure Properties

IsLREGclosed under union?

1=L[r1],L2=L[r2]

1?L2=L[(r1+r2)]

07-23:Closure Properties

IsLREGclosed under complementation?

Given anyDFAM= (K,Σ,δ,s,F), createM?= (K?,Σ?,δ?,s?,F?)such thatL[M?] = L[M]

07-24:Closure Properties

IsLREGclosed under complementation?

Given anyDFAM= (K,Σ,δ,s,F), createM?= (K?,Σ?,δ?,s?,F?)such thatL[M?] = L[M]

K?=K

s?=s

F?=K-F

07-25:Closure Properties

IsLREGclosed under intersection?

07-26:Closure Properties

IsLREGclosed under intersection?

A?B=A∩B

(diagram on board)

We can also use a direct construction

L1=all strings over{a,b}that begin withaa

L2=all strings over{a,b}that end withaa

ConstructL1∩L2

07-27:Closure Properties

Given DFAM1= (K1,Σ1,δ1,s1,F1)and DFAM2= (K2,Σ2,δ2,s2,F2), create DFAMsuch thatL[M] =

L[M1]∩L[M2]

07-28:Closure Properties

GivenM1= (K1,Σ1,δ1,s1,F1)andM2= (K2,Σ2,δ2,s2,F2), createMsuch thatL[M] =L[M1]∩L[M2]

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization7

K=K1×K2

Σ = Σ1= Σ2

δ={(((q1,q2),a),(q?1,q?2)) : ((q1,a),q?1)?δ1,((q2,a),q?2)?δ2}

s= (s1,s2)

F={(f1,f2) :f1?F1,f2?F2}

07-29:State Minimization

Possible to have several different DFA that all accept the same language Redundant states - duplicate the effort of other states

07-30:State Minimization

b 34
b a,b 5 a a 1 2 0 a ba b a b

What isL[M]?07-31:State Minimization

b 34
b a,b 5 a a 1 2 0 a ba b a b

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization8

07-32:State Minimization

34
a,b 7 a a 1 2 0 aa b a b 56
a a b b bb b

07-33:State Minimization

Two statesq1andq2are equivalent if:

Every string that drivesq1to an accept state also drivesq2to an accept state Every string that drivesq2to an accept state also drivesq1to an accept state

07-34:State Minimization

Two statesq1andq2of DFAMare equivalent if:

?w?Σ?,((q1,w)?→?M(f1,?)?

(q2,w)?→?M(f2,?)?f1?FM)?f2?FM

07-35:State Minimization

Two statesq1andq2are equivalent with respect to a stringwif and only if ((q1,w)?→?M(f1,?)? (q2,w)?→?M(f2,?)?f1?FM)?f2?FM and ((q1,w)?→?M(q3,?)? (q2,w)?→?M(q4,?)?q3??FM)?q4??FM Two statesq1andq2are equivalent if they are equivalent with respect to all stringsw?Σ?

07-36:State Minimization

How do we determine if two statesq1andq2are equivalent? Check to see if they are equivalent with respect to strings oflength 0

07-37:State Minimization

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization9

How do we determine if two statesq1andq2are equivalent? Check to see if they are equivalent with respect to strings oflength 0 Check to see if they are equivalent with respect to strings oflength 1

07-38:State Minimization

How do we determine if two statesq1andq2are equivalent? Check to see if they are equivalent with respect to strings oflength 0 Check to see if they are equivalent with respect to strings oflength 1 Check to see if they are equivalent with respect to strings oflength 2 .. and so on

07-39:State Minimization

When areq1andq2equivalent with respect to all strings of length 0?

07-40:State Minimization

When areq1andq2equivalent with respect to all strings of length 0? Bothq1andq2are accept states, or neitherq1norq2are accept states

07-41:State Minimization

Two statesq1andq2are equivalent with respect to all strings of lengthnif ..

Hint: Think inductively

07-42:State Minimization

Two statesq1andq2are equivalent with respect to all strings of lengthnif ..

Hint: Think inductively

Hint 2: If we knew which states were equivalent with respect to all strings of lengthn-1...

07-43:State Minimization

Two statesq1andq2are equivalent with respect to all strings of lengthnif, for alla?Σ

((q1,a),q3)?δ[δ(q1,a) =q3]

((q2,a),q4)?δ[δ(q2,a) =q4]

q3andq4are equivalent with respect to all strings of lengthn-1

07-44:State Minimization

Equivalence matrixE(i):

Only need to calculate upper triangle of matrix (why?)

E(?)[i,j] = 1iffq1andqjare equivalent with respect to all strings (that is, ifq1andqjare equivalent)

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization10

07-45:State Minimization

E(0):

E(0)[i,j] =...

07-46:State Minimization

E(0):

E(0)[i,j] = 1ifqiandqjare both accept states, or both non-accept states E(0)[i,j] = 0ifqiis an accept state, andqjis not an accept state E(0)[i,j] = 0ifqiis not an accept state, andqjis an accept state

07-47:State Minimization

E(n)[i,j] = 1if, for alla?Σ

((qi,a),qk)?δ[δ(qi,a) =qk]

((qj,a),ql)?δ[δ(qj,a) =ql]

E(n-1)[qk,ql] = 1

07-48:State Minimization

CreatingE(?):

First, createE(0)

fori= 0to n forj= (i+ 1)ton if(qi?F?qj?F)?(qi??F?qj??F)

E[i,j] = 1

else

E[i,j] = 0

07-49:State Minimization

Repeat:

fori= 0to n forj= (i+ 1)ton for eacha?Σ k=δ(i,a) l=δ(j,a) ifE[k,l] == 0 setE[i,j] = 0

Until no changes are made07-50:State Minimization

Given any DFAM, we can create an equivalent DFA with the minimum number of states as follows:

CalculateE(?), to find equivalent states

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization11

While there is a pairqi,qjof equivalent states inM Change all transitions intoqjto transitions toqi

Removeqjand all transitions out ofqj

Finally do a DFS form the initial state, and remove all statesnot reachable from the initial state

07-51:State Minimization Example

01 4 2 53
6 ab a bb b b a a a a b a,b

07-52:State Minimization Example

0123456

0011011

100100

21011
3011
400
51
01 4 2 53
6 ab a bb b b a a a a b a,b

07-53:State Minimization Example

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization12

0123456

0001000

100100

20011
3000
400
51
01 4 2 53
6 ab a bb b b a a a a b a,b

07-54:State Minimization Example

0123456

0001000

100100

20010
3000
400
50
01 4 2 53
6 ab a bb b b a a a a b a,b

07-55:State Minimization Example

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization13

01 4 2 53
6 ab a bb b b a a a a b a,b

07-56:State Minimization Example

012 6 b abquotesdbs_dbs17.pdfusesText_23

[PDF] [PDF] CS411-2015S-07 Non-Regular Languages Closure Properties of

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization1

07-0:Fun with Finite Automata

L={0n1n:n >0}

 {01, 0011, 000111, 00001111, ...}

07-1:Fun with Finite Automata

L={0n1n:n >0}is not regular!

Why?

Finite number of states (DFA)

Unbounded number of 0"s before the 1"s

07-2:Non-Regular Languages

Pigeonhole Principle:

More transitions than states

07-3:Non-Regular Languages

Break string intow=xyz

07-4:Pumping Lemma

If a languageLis regular, then:

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization2

y?=?

 |xy|< n

xyiz?Lfor alli≥0

07-5:Using the Pumping Lemma

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

 |xy|< n

y?=?

There is anisuch thatxyiz??L

Conclude thatLmust not be regular

07-6:Using the Pumping Lemma

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

 |xy|< n

y?=?

There is anisuch thatxyiz??L

Conclude thatLmust not be regular

L={0n1n:n >0}

07-7:Using the Pumping Lemma

L={0n1n:n >0}

Letnbe the constant of the pumping lemma

Consider the stringw= 0n1n

If we breakw=xyzsuch that|xy|< n,|y|>0,

x= 0j,y= 0k,z= 0n-k-j1n

Considerw?=xy2z= 0n+k1nfor some0< k < n

w???L

Lis not regular (by the pumping lemma)

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization3

07-8:Using the Pumping Lemma

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

 |xy|< n

y?=?

There is anisuch thatxyiz??L

Conclude thatLmust not be regular

L={ww:w?(a+b)?}07-9:Using the Pumping Lemma

L={ww:w?(a+b)?}

Letnbe the constant of the pumping lemma

Considerw=anbanb?L

If we breakw=xyzsuch that|xy|< n,|y|>0,

x=aj,y=ak,z=an-k-jban

07-10:Using the Pumping LemmaYou have an adversary who thinksLis regular. You need to prove that your adversary is wrong.

07-11:Using the Pumping Lemma

Your adversary picks ann

You pick aw?L(such that|w|> n)

You pick anisuch thatxyiz??L

07-12:Using the Pumping Lemma

CS411-2015S-07Non-Regular Languages

Closure Properties of Regular Languages

DFA State Minimization4

Your adversary picks ann

You pick aw?L(such that|w|> n)

You pick anisuch thatxyiz??L

L={0n1n:n >0}

{01, 0011, 000111, 00001111, ...}

L={0n1n:n >0}is not regular!

Why?

Finite number of states (DFA)

Unbounded number of 0"s before the 1"s

Pigeonhole Principle:

More transitions than states

Break string intow=xyz

If a languageLis regular, then:

y?=?

|xy|< n

xyiz?Lfor alli≥0

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

|xy|< n

y?=?

Conclude thatLmust not be regular

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

|xy|< n

y?=?

Conclude thatLmust not be regular

Letnbe the constant of the pumping lemma

Consider the stringw= 0n1n

If we breakw=xyzsuch that|xy|< n,|y|>0,

x= 0j,y= 0k,z= 0n-k-j1n

Considerw?=xy2z= 0n+k1nfor some0< k < n

w???L

Lis not regular (by the pumping lemma)

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

|xy|< n

y?=?

Conclude thatLmust not be regular

Letnbe the constant of the pumping lemma

Considerw=anbanb?L

If we breakw=xyzsuch that|xy|< n,|y|>0,

x=aj,y=ak,z=an-k-jban

Your adversary picks ann

You pick aw?L(such that|w|> n)

You pick anisuch thatxyiz??L

Your adversary picks ann

You pick aw?L(such that|w|> n)

You pick anisuch thatxyiz??L

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

|xy|< n

y?=?

Conclude thatLmust not be regular

Letnbe the constant of the pumping lemma

Considerw=anbn-1?L

If we breakw=xyzsuch that|xy|< n,|y|>0,

x=aj,y=ak,z=an-k-jbn-1

AssumeLis regular

Letnbe the constant of the pumping lemma

Create a stringwsuch that|w|> n

|xy|< n

y?=?

Conclude thatLmust not be regular

Letnbe the constant of the pumping lemma

Considerw=a2nb?L

If we breakw=xyzsuch that|xy|< n,|y|>0,

x=aj,y=ak,z=a2n-k-jb

As long as k is even,w?=xyiz?Lfor alli

No! We may not have chosen a clever enoughw

How can we prove thatLis regular?

No! We may not have chosen a clever enoughw

How can we prove thatLis regular?

IsLREGclosed under union?

IsLREGclosed under complementation?

IsLREGclosed under intersection?

IsLREGclosed under union?

IsLREGclosed under union?

IsLREGclosed under complementation?

IsLREGclosed under complementation?