Search code examples
automataformal-languages

Show that, for any languages L1 and L2, we have (1). L1L1^* = L1^*L1L1^*

I am taking Automata Theory and Formal Languages and am confused on how to work out #3 from my HW. The link to HW is provided in the following: https://www.eecs.wsu.edu/~zdang/c317/Assignments/homework1.pdf

For 3.1 I know that L1L1^* is essentially the same as saying L1^* L1L1^* but dont know how to express it. Would I be able to say if I divide both sides by L1 we have, L1^* = L1^* L1^* thus L1^* = L1^* ?

For 3.2 we are given the equation (L1^* L2)^* = (L1 + L2)^* . To prove the right hand side I know we can take L1^* followed by L2 over and over making it the same as the left hand side. Again I am unsure how to express this.

Any help would be greatly appreciated.

Solution

  • To show L1L1* = L1*L1L1* we need to show L1L1* contains everything in L1*L1L1* and vice versa.

    • L1L1* contains everything in L1*L1L1*. The latter contains strings in L1^aL1L1^b for all nonnegative integers a and b. By associativity of concatenation we can rewrite L1^aL1L1^b as L1L1^(a+b) which must be in L1L1*.

    • L1*L1L1* contains everything in L1L1*. The latter contains strings in L1L1^b. By the zero of exponentiation we have L1^0 = {empty string} and by language concatenation and string concatenation with the empty string we can see that L1^0L1L1^b = L1L1^b. But L1^0L1L1^b is in L1*L1L1* by choosing to repeat the first L1* zero times.

    It is not true that (L1*L2)* = (L1+L2)*. To see this, note simply that the latter contains everything in L1 while the latter does not (for non-trivial L2). That is, L1 can be obtained from the latter by repeating just once and then choosing L1, but to get any L1 from the former we must repeat at least once which forces at least one L2.