Let be a finite alphabet (i.e., a finite set of letters), and be the empty sequence. We define the shuffle of two words as follows.
For every ,
For every and ,
Furthermore, for two languages , their shuffle is defined by:
For example, we have:
Answer the following questions.
(1) Compute .
(2) Suppose that deterministic finite automata and accept languages and , respectively. Here, and are respectively the set of states, the transition function, the initial state, and the set of final states of . You may assume that the transition functions are total functions. Give a non-deterministic automaton that accepts .
(3) Prove the correctness of your answer for question (2) above.
(4) Let and . Prove that is not a context-free language. Here, you may use the pumping lemma for context-free languages.