CS 390 Solutions to Unit 4 Exercises

pp. 37 - 38

1.38 Since

and

, the difference between them is L⁰ which is equal to {

}. Hence L^* = L⁺ if and only if

is in L.

1.40 (a) For example let L₁ = { a } and L₂ = { aa }.

1.43 We are going to prove L^*

( L⁺ )^*

( L^* )⁺

( L^* )^*

L^* . That will prove that all those languages are equal.

(1) L^*

( L⁺ )^* :
Let x be an arbitrary nonempty string of L^*. Then there are strings w₁, w₂, ..., w_k in L such that x = w₁w₂...w_k. Since w₁, w₂, ..., w_k are strings of L, they are also in L⁺. Hence x = w₁w₂...w_k is in (L⁺)^k. Hence it is in ( L⁺ )^*. If x is an empty string, then it is obviously in ( L⁺ )^*.
Hence L^*

( L⁺ )^* holds.

(2) ( L⁺ )^*

( L^* )⁺ :
Let x be an arbitrary nonempty string of ( L⁺ )^*. Then there are strings w₁, w₂, ..., w_k in L⁺ such that x = w₁w₂...w_k. Since w₁, w₂, ..., w_k are strings of L⁺, they also belong to L^*. Also since x is a nonempty string, at least one w_i is nonempty. Hence x is in (L^* )^m for some non-zero integer m. Hence x is in ( L^* )⁺.
If x is empty, then since the empty string is in L^*, it is also in ( L^* )⁺.
Hence ( L⁺ )^*

( L^* )⁺ .

(3) ( L^* )⁺

( L^* )^* :
Since X⁺

X^* holds for any language X, it holds for L. Hence ( L^* )⁺

( L^* )^* .

(4) ( L^* )^*

L^* :
Let x be an arbitrary nonempty string of ( L^* )^*. Then there are nonempty strings w₁, w₂, ..., w_k in L^* such that x = w₁w₂...w_k. Since w₁, w₂, ..., w_k are strings of L^*, for each w_i there are strings w_i1, w_i2, ..., w_{im_i} in L such that w_i = w_i1w_i2...w_{im_i}
Hence x = w₁₁ ...w_1m₁w₂₁...w_2m₂...w_m1...w_{mm_k} . Hence x is in L^* .
If x is an empty string, then it is obviously in L^* .
Hence ( L^* )^*

L^* .