Question

For each of the following statements. state whether it is True or False. Prove your answer: a. ∀L1 , L2(L1= L2)iff L1*·=L2*). b. (ØuØ*)n(¬Ø- (ØØ*)) = Ø (where ¬Ø is the complement of Ø). c. Every infinite language is the complement of a finite language. d. ∀L ((LR)R = L). e. ∀L1, L2((L1L2)*= L1*L2*). f. ∀L1, L2(( ((L1*L2*L1*)*= (L2UL1)*). g . ∀L1, L2(( ( ( L 1 U L 2 ) * = L 1 * U L 2 * ) . h. ∀L1, L2((,L3((L1UL2)L3= (L1L3)U(LzLJ)). i. ∀L1, L2, L3 ((L,L2) U L3 = (L1U L3) (L2 U L3)) j. ∀L ((L+)* = L*). k. ∀L (ØL* = {e}). I. VL(ØUL+= L*). m. VL1, L2 ((L1 U L2)* = (L2 U L1)*). the * indicates the set of possible strings. The set of all possible strings over an alphabet is indicated by Σ* L consists of all strings that can be formed by taking some strings in {a,b}* Where a, b are elements of L and some psossible strings that can be formed include, a, aa, bb, aaabb, etc.

Answer 1

a. ∀L1 , L2 (L1= L2)iff L1*·=L2*).

answer: True

proof: let L1, L2 are two languages (i.e. set of strings)

let L1=Ø and L2=Ø then L1*={} L2*={}

therefore if L1=L2 then L1*=L2* similarly if L1*=L2* then L1=L2;

for any ={a,b} if L1*={,a,aa,aaa,......}={a}* and L2*={,a,aa,aaa,......}={a}* then L1=L2={a}

hence the given statement is proved.

b. (ØuØ*)n(¬Ø- (ØØ*)) = Ø (where ¬Ø is the complement of Ø).

soution: according algebraic laws of formal languages.

Ø*={} , ØuØ*={} , and  ØØ*=Ø

¯=a non empty set (ie. universal set)

¬Ø- (ØØ*)=universal set - Ø=universalset. the universal set may also include .

therefore (ØuØ*)n(¬Ø- (ØØ*)) = Ø is not true.

c. Every infinite language is the complement of a finite language.

Answer : False

Let L is a language , L={ set of all possible even length strings } is an infinite set.

then ¬L ={set of all possible odd length strings} is also an infinite set.

therefore there may be some infinite sets whose complement is also infinite set.

d. ∀L ((L^R)^R = L).

Solution: True.

let L={ab,abb} then L^R= {ba,bba} and (L^R )^R={ab,bba}=L

hence ∀L ((L^R)^R = L) is true.

e. ∀L1, L2((L1L2)*= L1*L2*).

Solution:- False

proof by example:

let L1={a}, L2={b} L1*={,a,aa,aaa,aaaa...} , L2*={,b,bb,bbb,bbbb,....}

L1*L2*= {,a,b,ab,aa,bb,aaa,aab,abb,bbb,aabb,aaaa,bbbb,.....}

L1L2={ab}, (L1L2)*= {,ab,abab,ababab,abababab,......}

hence  ∀L1, L2((L1L2)*= L1*L2*) is not true

f. ∀L1, L2(( ((L1*L2*L1*)*= (L2UL1)*).

Solution:True.

according to algebraic laws of regular expressions (R1+R2)* = (R1*R2*)*

therefore (R1*R2*R1*)*=(R1+R2+R1)*=(R1+R2)* where R1,R2 are regular expressions.

if L(R1)=L1, L(R2)=L2 then  ( L1*L2*L1*)*= (L2UL1)*.

hence ∀L1, L2(( ((L1*L2*L1*)*= (L2UL1)*) is true.

g . ∀L1, L2(( ( ( L 1 U L 2 ) * = L 1 * U L 2 * ) .

Solution: False.

let R1,R2 are two regular expressions and L(R1)=L1 and L(R2)= L2

(R1+R2)*=(R1*R2*)* R1*R2*

L((R1+R2)*)=(L(R1)*L(R2)*)* L(R1)*L(R2)*

hence ∀L1, L2(( ( ( L 1 U L 2 ) * = L 1 * U L 2 * ) is false

h. ∀L1, L2((,L3((L1UL2)L3= (L1L3)U(L2L3)).

Answer:True

solution:

let L1={a,b} , L2={x,y}, L3={c}

L1UL2={a,b,x,y} , (L1UL2)L3={ac,bc,xc,yc} ----->(1)

L1L3={ac,bc] , L2L3={xc,yc} , L1L3UL2L3={ac,bc,xc,yc} -------->(2)

from (1), (2) , it is proved that the given statement ∀L1, L2((,L3((L1UL2)L3= (L1L3)U(L2L3)) is true.

i. ∀L1, L2, L3 ((L,L2) U L3 = (L1U L3) (L2 U L3))

Answer:False

solution: Let L1={a,b} , L2={x,y}, L3={c}

L1L2={ax,ay,bx,by}, L1L2UL3={ax,bx,ay,by,c} ----->(1)

L1UL3={a,b,c}, L2UL3={x,y,c} therefore (L1UL3)(L2UL3)={ax,ay,ac,bx,by,bc,cx,cy,cc} ------->(2)

(1) and (2) are not equal , hence the given statement ∀L1, L2, L3 ((L,L2) U L3 = (L1U L3) (L2 U L3)) is false.

j. ∀L ((L+)* = L*).

Answer: True.

solution:

(L*)*=L* and (L⁺)⁺= L⁺

L⁺=LL*

L*={}UL⁺

(L⁺)*={}U(L⁺)⁺= {}U(L⁺)=L*

hence given statement is true.

k. ∀L (ØL* = {e}).

Answer: Fals

for any language L ,  ØL=Ø where Ø is empty set.

therefore ØL*=Ø

hence  ∀L (ØL* = {e}) is false.

I. L(ØUL+= L*).

Answer: false

solution:

for any language L,  ØUL =L where Ø is empty set.

therefore ØUL+=L+

hence L(ØUL+= L*) is false

m. L1, L2 ((L1 U L2)* = (L2 U L1)*).

Answer: True.

According algebraic laws of formal languages, union is commutative

L1UL2=L2UL1

Let R1,R2 are regular expressions with L(R1)=L1 and L(R2)=L2 respectively.

according to regular expressions (R1+R2)*=(R2+R1)*

therefore L((R1+R2)*))=L((R2+R1)*)

i.e (L1UL2)*=(L2UL1)*

hence the given statment L1, L2 ((L1 U L2)* = (L2 U L1)*) is true.