7/29/2019 Propiedades NO Regulares

1/3

Suppose L is a non-regular language.Can we concludethat Lc

is not regular?

The answer is yes. We will prove that "IfL is not regular, thenLc is not regular" using a proof

by contradiction.

o We begin with the knowledge thatL is not regular.o Assume thatLc is regular.o Then the language (Lc)c must be regular since regular languages are

closed under complement.

o However, (Lc)c = L which means thatL is regular.o This is a contradiction since we began with the knowledge thatL is

not regular.

o Therefore, our assumption thatLc is regular must be false.o Therefore, we can conclude thatLc is not regular.

Suppose L and L'are non-regular languages.Can we concludethat L union L'is

not regular?

The answer is no. We will prove that "IfL andL'are not regular, thenL unionL'is not

regular" is a FALSE statement by giving a counterexample.

o LetL be the set of palindromes over the alphabet {A,B}.o L is not a regular language.

This is a fact we can prove after next week using thepumping Lemma.

For now, you must accept the truth of this statement.

o LetL'=Lc.o L'is not a regular language.

We knowL is not regular from above. We know thatLc is not regular because the non-regular

languages are closed under complement.

L'=Lc.o L unionL'= *

As we observed before, the union of any language and itscomplement is *.

o * is a regular language.o Therefore, we can conclude the assertion that "IfL andL'are not

regular, thenL unionL'is not regular" is FALSE because we have

given a counterexample that contradicts it.

http://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/2.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/2.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/2.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/4.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/4.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/4.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/4.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/2.html

7/29/2019 Propiedades NO Regulares

2/3

Suppose L and L'are non-regular languages.Can we

concludethat L intersection L'is not regular? The answer is no. We will prove that "IfL andL'are not regular, thenL intersectionL'is not

regular" is a FALSE statement by giving a counterexample.

o LetL be the set of palindromes over the alphabet {A,B}.o L is not a regular language.

This is a fact we can prove after next week using thepumping Lemma.

For now, you must accept the truth of this statement.o LetL'=Lc.o L'is not a regular language.

We knowL is not regular from above. We know thatLc is not regular because the non-regular

languages are closed under complement.

L'=Lc.o L intersectionL'= {}

As we observed before, the intersection of any language andits complement is {}

o {} is a regular language.o Therefore, we can conclude the assertion that "IfL andL'are not

regular, thenL intersectionL'is not regular" is FALSE because we

have given a counterexample that contradicts it.

Suppose L and L'are non-regular languages.Can we concludethat L - L'is not

regular?

The answer is no. We will prove that "IfL andL'are not regular, thenL - L'is not regular" is a

FALSE statement by giving a counterexample.

o Let bothL andL'be the set of palindromes over the alphabet {A,B}.o L andL'are not a regular languages.

This is a fact we can prove after next week using the pumpingLemma.

For now, you must accept the truth of this statement.o L - L'= {}o {} is a regular language.o Therefore, we can conclude the assertion that "IfL andL'are not

regular, thenL - L'is not regular" is FALSE because we have given a

counterexample that contradicts it.

http://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/6.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/6.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/6.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/6.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/8.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/8.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/8.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/8.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/6.htmlhttp://www.cse.msu.edu/~torng/360Book/RegLang/Properties/Answers/6.html

7/29/2019 Propiedades NO Regulares

3/3

(a) It is possible that the concatenation of two nonregular languages is regular.

True. To prove this, we need one example: Let L1 = {aibj, i, j 0 and ij}. Let L2 = {b

na

m, n,

m 0 and nm. L1L2 = {aibja

ksuch that:

Ifiand kare both 0 then j 2. Ifi= 0 and k 0 then j 1. Ifi 0 and k= 0 then j 1. Ifiand kare both 1 then j 1. Otherwise,j 0}.In other words, L1L2 is almost a*b*a*, with a small number of exceptions that can be

checked for by a finite state machine.

(a) IfL is a language that is not regular, then L* is not regular.

False.

Let L = Primea = {an

: n is prime}. L is not regular.

L* = {} {an

: 1 < n}. L* is regular.