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

标签：

• Tokyo-University
• Language-Shuffle
• Nondeterministic-Finite-Automaton
• Pumping-Lemma

Author

Description

Let $\Sigma$ be a finite alphabet (i.e., a finite set of letters), and $\epsilon$ be the empty sequence. We define the shuffle $w_1 \otimes w_2 \subseteq \Sigma^*$ of two words $w_1, w_2 \in \Sigma^*$ as follows.

• For every $w \in \Sigma^*$,

$$\epsilon \otimes w = w \otimes \epsilon = \{w\}.$$

• For every $a, b \in \Sigma$ and $w_1, w_2 \in \Sigma^*$,

$$(aw_1) \otimes (bw_2) = \{aw \mid w \in w_1 \otimes (bw_2)\} \cup \{bw \mid w \in (aw_1) \otimes w_2\}.$$

Furthermore, for two languages $L_1, L_2 \subseteq \Sigma^*$, their shuffle $L_1 \otimes L_2 \subseteq \Sigma^*$ is defined by:

$$L_1 \otimes L_2 = \bigcup_{w_1 \in L_1, w_2 \in L_2} w_1 \otimes w_2.$$

For example, we have:

$$\{ab, ba\} \otimes \{\epsilon, c\} = (ab \otimes \epsilon) \cup (ab \otimes c) \cup (ba \otimes \epsilon) \cup (ba \otimes c) = \{ab, cab, acb, abc, ba, cba, bca, bac\}.$$

Answer the following questions.

(1) Compute $\{a, bb\} \otimes \{ab, cc\}$.

(2) Suppose that deterministic finite automata $\mathcal{A}_1 = (Q_1, \Sigma, \delta_1, q_{1,0}, F_1)$ and $\mathcal{A}_2 = (Q_2, \Sigma, \delta_2, q_{2,0}, F_2)$ accept languages $L_1$ and $L_2$, respectively. Here, $Q_i, \delta_i, q_{i,0},$ and $F_i$ are respectively the set of states, the transition function, the initial state, and the set of final states of $\mathcal{A}_i \ (i \in \{1, 2\})$. You may assume that the transition functions $\delta_i \in Q_i \times \Sigma \rightarrow Q_i\ (i \in \{1, 2\})$ are total functions. Give a non-deterministic automaton that accepts $L_1 \otimes L_2$.

(3) Prove the correctness of your answer for question (2) above.

(4) Let $L_3 = \{a^nb^n \mid n \geq 0\}$ and $L_4 = \{c^md^m \mid m \geq 0\}$. Prove that $L_3 \otimes L_4$ is not a context-free language. Here, you may use the pumping lemma for context-free languages.

Kai