Please show how to prove the answer 3) For each of the following statements, sta

Question

Please show how to prove the answer

3) For each of the following statements, state whether it is True or False. Prove your answer VLi, L2 (Li = L2 iffLi'-L:"). a) b) (Hint: Try to find counterexample) Every infinite language is the complement of a finite language. (Hint: Try to find counterexample) c) YL ((LR)R-L). d) VL,, L2 , ((Li L2)" = Li * L:"). (Hint: Try to find a counterexample) e) VL, L2 (Li UL2)* LL2*. (Hint: Try to find a counterexample) f) VLi, L2,L3 ((Li L2) L3 = (LJU L3) (L2 U Lj). (Hint: Try to find a counterexample) g) VL ((LL(Hint: Consider definition of L)

Explanation / Answer

a)True , L1=L2 iff L1*=L2*

L1*={0,01,0,01...} L2*={0,01,0,01...}

L1={0,01}

L2={0,01}

b) False in ,

e) True as in

L1= { 0, 01} and L2 = {1, 01} L1*={0,01,0,01...} L2*={1,01,1,01,...}

L1L2 = {01,001,011,0101}

L1L2* = {01,001,011,0101,01,001,011,0101...}

L1*L2*={01,001,01,001,011,0101,001,0101,..}

f) True

A formal language (or just language) is a set of
strings

We should prove that (L1 L2)L3 = (L1L3 )( L2L3). I prove that using the following property: let A,B be two sets, A = B A B A B. A B. We have to prove that x A x B. Let x (L1 L2)L3. x (L1L2)L3 u, v : x = uv, u (L1 L2) v L3 u (L1 L2) u L1 u L2 ifu L1 uv L1L3 uv (L1L3 )( L2L3) ifu L2 uv L2L3 uv (L1L3) (L2L3)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.