Ask Question
4 October, 17:43

9. Which of the following are true for all regular languages and all homomorphisms? (a) h (L1 ∪ L2) = h (L1) ∩ h (L2). (b) h (L1 ∩ L2) = h (L1) ∩ h (L2). (c) h (L1L2) = h (L1) h (L2).

+5
Answers (1)
  1. 4 October, 19:19
    0
    h (L1 ∪ L2) = h (L1) ∩ h (L2).

    This is true.

    There will be w ∈ (L1 ∪ L2) for any s ∈ h (L1 ∪ L2) in such a way that s=h (w)

    we can assume that w ∈ L1

    So In this case h (w) ∈ L (S1). Hence s ∈ L (S1)

    for any s ∈ h (L1) U h (L2)

    We can assume that s ∈ L (S1)

    There exists w ∈ L1 such that s = h (w)

    In this case it is w ∈ L1 U L2 as well.

    Hence, s ∈ h (L1 U L2)

    Explanation

    consider = 0,1 and = a, b and h (0) = a, h (1) = ab

    (a) Consider L1 = 10,01 and L2 = 00,11

    Now L1 ∪ L2 = 00,01,10,11

    h (L1 ∪ L2) = h (00), h (01), h (10), h (11) = h (0) h (0), h (0) h (1), h (1) h (0), h (1) h (1)

    = aa, aab, aba, abab

    Hence h (L1 ∪ L2) = aa, aab, aba, abab.

    Here h (L1) = h (10), h (01) = h (1) h (0), h (0) h (1) = aba, aab

    Hence h (L1) = aba, aab.

    Here h (L2) = h (00), h (11) = h (0) h (0), h (1) h (1) = aa, abab

    Hence h (L2) = aa, abab.

    Finally Hence, h (L1 ∪ L2) = h (L1) ∩ h (L2).
Know the Answer?
Not Sure About the Answer?
Get an answer to your question ✅ “9. Which of the following are true for all regular languages and all homomorphisms? (a) h (L1 ∪ L2) = h (L1) ∩ h (L2). (b) h (L1 ∩ L2) = h ...” in 📙 Computers & Technology if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers