Peter Linz 4th edition Ex-1.2 -Q10

Question

Q- Prove or Disprove the following claim-
                                                                     $(L^R)^*=(L^*)^R$
for all languages.

Comments

oh yes

just start state and final state will change in the DFA and arrow reverses

---

So the conclusion is -  $(L^R)^∗=(L^∗)^R$ ?

---

yes

no counter

Answer 1

Let take L = { W₁ , W₂, W₃, W₄, ........}

my convention is ( W_i )^R = X_i.

we know that (W₁.W₂ )^R = (X₂ . X₁)

ex:- let W₁ = ab ( this means X₁ = ba ), W₂ = cd ( this means X₂ = dc ) ===> (W₁ . W₂)^R = (ab.cd)R = (dc . ba) = (X₂. X₁)

 

what is L* ?

L* ={ ∈, L , L², L³,.......} (simply concentrate on L² only )

    = { ∈, ( W₁ , W₂, W₃, W₄, .......) , ( W₁W₁ , W₁W₂, W₁W₃, W₁W₄, .......) , ( W₂W₁ , W₂W₂, W₂W₃, W₂W₄, .......) , .....  }

 

( L* )^R = simply reverse each string in the L*

  = { ∈, ( (W₁)^R, (W₂)^R, (W₃)^R, .......) , ( ( W₁W₁)^R , (W₁W₂)^R, (W₁W₃)^R, .......), ( ( W₂W₁)^R , (W₂W₂)^R, (W₂W₃)^R,  .......), .....  }

  = { ∈, ( (X₁), (X₂), (X₃), (X₄), ...........) , ( ( X₁X₁) , (X₂X₁), (X₃X₁), .................), ( (X₁X₂) , (X₂X₂), (X₃X₂), , .......), .....  }

 

what is L^R ?

L^R = reverse each element in the language

   = { (W₁)^R, (W₂)^R, (W₃)^R, ......}

  = { (X₁), (X₂), (X₃), (X₄), ........... }

 

(L^R)* = {∈, ( (X₁), (X₂), (X₃), (X₄), ...........) , ( ( X₁X₁) , (X₁X₂), (X₁X₃), .................), ( (X₂X₁) , (X₂X₂), (X₂X₃), , .......), .....}

       = { ∈, ( (X₁), (X₂), (X₃), (X₄), ...........) , ( ( X₁X₁) , (X₂X₁), (X₃X₁), .................), ( (X₁X₂) , (X₂X₂), (X₃X₂), , .......), .....  }

       = (L*)^R

 

NOTE :-

  word X_i . X_j is in ( L^R )^* it must be in ( (L*)^R) converse also.

think why this is true? if you didn't get in general, take the sample strings and realize how it should be true.

Comments

Thanks a lot shaik sir :)

---

@Soumya29 mam

pleasure is Mine

Answer 2

I take eg for the above statements:

1) lets L = a^* ,

LHS:  (L^*)^R =  (((a^*)^*)^R)

                     =  ((a)^*)^R   (because a^* accepts all combination of a's including epsilon)

so reverse of a^* accepts phi.

RHS: (L^R)^* = ((a^*)^R)^*

                    ⁼ (a)^*

                    = a^*

so this is  equal.

please verify it...

           

Comments

Shaik Masthan (L^R)^* = (L^*)^R , this condition is true na??

---

i hope so, i am not getting any counter example.

But i am not able to proof formally.

---

i added formal proof for the statement, just check it.