High School

Let [tex]\Sigma_i[/tex] be alphabets for [tex]i = 1, 2, 3[/tex], and [tex]L_i \subseteq \Sigma_i^*[/tex] for [tex]i = 1, 2, 3[/tex] be three languages. Prove the following:

(a) [tex]L_1 (L_2 \cup L_3) = L_1 L_2 \cup L_1 L_3[/tex]

(b) [tex](L_1 \cap L_2) L_3 \neq L_1 L_3 \cap L_2 L_3[/tex], in general.

(c) [tex]L_1 (L_2 - L_3) \neq L_1 L_2 - L_1 L_3[/tex], in general.

(d) [tex](L_1 \cup L_2)^* = (L_1^* L_2^*)^*[/tex]

Answer :

We can write `(L1 ∪ L2)* = (L1* L2*)*`.Hence, `(d)` is proved.

d) We know that `(L1 ∪ L2)* ⊆ (L1* L2*)*`.

Therefore, every string in `(L1 ∪ L2)*` is also in `(L1* L2*)*`.

To prove that `(L1* L2*)* ⊆ (L1 ∪ L2)*`, let's take any string `s` in `(L1* L2*)*`.

It means that `s` can be written as `s = s1s2 ... sn`, where each `si` is a string in `L1* ∪ L2*`.

Therefore, every `si` is either a string in `L1*` or a string in `L2*`.

Therefore, every `si` is definitely in `(L1 ∪ L2)*`.

Hence, every string in `(L1* L2*)*` is definitely in `(L1 ∪ L2)*`.Therefore, `(L1* L2*)* ⊆ (L1 ∪ L2)*` is proved.

Now, we can write `(L1 ∪ L2)* = (L1* L2*)*`.Hence, `(d)` is proved.

Know more about string here:

https://brainly.com/question/30392694

#SPJ11

Other Questions