Suppose L1, L2 are two regular languages over the alphabet Σ = {a, b}. Consider the following two new languages: shuffle1(L1, L2) = {a1b1 . . . anbn : a1 . . . an ∈ L1, b1 . . . bn ∈ L2, ai, bi ∈ Σ, ai = bi, i ∈ [1 . . . n]} shuffle2(L1, L2) = {a1b1 . . . anbn : a1 . . . an ∈ L1, b1 . . . bn ∈ L2, ai, bi ∈ Σ, an−(i−1) = bi, i ∈ [1 . . . n]} Notice how shuffle1, shuffle2 are similar, but not quite the same. One of them is necessarily regular and the other is not necessarily regular. Which is which? Prove your answer. If part of your proof relies on a construction, you do not need to prove its correctness.
Suppose L1, L2 are two regular languages over the alphabet Σ = {a, b}. Consider the following two new languages:
shuffle1(L1, L2) = {a1b1 . . . anbn : a1 . . . an ∈ L1, b1 . . . bn ∈ L2, ai, bi ∈ Σ, ai = bi, i ∈ [1 . . . n]}
shuffle2(L1, L2) = {a1b1 . . . anbn : a1 . . . an ∈ L1, b1 . . . bn ∈ L2, ai, bi ∈ Σ, an−(i−1) = bi, i ∈ [1 . . . n]}
Notice how shuffle1, shuffle2 are similar, but not quite the same. One of them is necessarily regular and the other is not necessarily regular.
Which is which? Prove your answer. If part of your proof relies on a construction, you do not need to prove its correctness.
Shuffle1(L1, L2) and shuffle2(L1, L2) are two new languages defined based on the shuffle operation of two regular languages L1 and L2. shuffle1(L1, L2) contains all strings that can be formed by interleaving the strings in L1 and L2, such that the corresponding symbols in the two strings are always the same. shuffle2(L1, L2) is similar, but with the additional requirement that the last symbol in each string must be the same.
The two languages are similar, but they have different properties. shuffle1(L1, L2) is always regular, while shuffle2(L1, L2) is not necessarily regular.
Step by step
Solved in 4 steps
