Reference no: EM132647730

1. We have language L over the alphabet {0,1}:
L={0^a1^a|a=0}.
We need to prove explicitly that there does not exist any deterministic finite automaton accepting/recognizing L. Solution has to be given without using pumping lemma for regularity.

2. Let S be the alphabet {0,1}, and K be a given regular language over S. Consider the following two languages:
K1={x?S^*|there exists a string y?S^*such that yx?K}
K2={x?S^*|there exists a string y?S^*such that xy?K}
Prove that both K1 and K2 are regular languages.

3. We have two languages L1 and L2 over the same alphabet S. Need to define the following language-operator:
ShuffleV1(L1, L2) = {w?S^*|w = x1y1...xkyk for some k=0, x1?L1, x2?L1,..., xk?L1 and y1?L2, y2?L2,..., yk?L2}.
For the languages L1 = {1}^* = {epsilon,1,11,111,1111,...}
L2 = {0},
the strings inShuffleV1(L1, L2) = ShuffleV1({1}*,{0}) with length at most three are: epsilon,0,00,10,000,010,100,110. In particular, epsilon is in ShuffleV1({1}*,{0}) because k can be 0, and the length three strings 101, 011, 001,and 111 are not in it because the last 1 is not followed by a 0. We need to prove that the language-operator ShuffleV1 preserves regularity: for all regular languages L1 and L2 over the alphabet S,ShuffleV1(L1, L2) is also regular.