跳到主要内容

東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年8月実施 専門科目I 問題1

Author

Description

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.

Kai