跳到主要内容

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

标签：

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 w1⊗w2⊆Σ∗w_1 \otimes w_2 \subseteq \Sigma^* of two words w1,w2∈Σ∗w_1, w_2 \in \Sigma^* as follows.

  • For every w∈Σ∗w \in \Sigma^*,
ϵ⊗w=w⊗ϵ={w}.\epsilon \otimes w = w \otimes \epsilon = \{w\}.
  • For every a,b∈Σa, b \in \Sigma and w1,w2∈Σ∗w_1, w_2 \in \Sigma^*,
(aw1)⊗(bw2)={aw∣w∈w1⊗(bw2)}∪{bw∣w∈(aw1)⊗w2}.(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 L1,L2⊆Σ∗L_1, L_2 \subseteq \Sigma^*, their shuffle L1⊗L2⊆Σ∗L_1 \otimes L_2 \subseteq \Sigma^* is defined by:

L1⊗L2=⋃w1∈L1,w2∈L2w1⊗w2.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}⊗{ϵ,c}=(ab⊗ϵ)∪(ab⊗c)∪(ba⊗ϵ)∪(ba⊗c)={ab,cab,acb,abc,ba,cba,bca,bac}.\{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}⊗{ab,cc}\{a, bb\} \otimes \{ab, cc\}.

(2) Suppose that deterministic finite automata A1=(Q1,Σ,δ1,q1,0,F1)\mathcal{A}_1 = (Q_1, \Sigma, \delta_1, q_{1,0}, F_1) and A2=(Q2,Σ,δ2,q2,0,F2)\mathcal{A}_2 = (Q_2, \Sigma, \delta_2, q_{2,0}, F_2) accept languages L1L_1 and L2L_2, respectively. Here, Qi,δi,qi,0,Q_i, \delta_i, q_{i,0}, and FiF_i are respectively the set of states, the transition function, the initial state, and the set of final states of Ai (i∈{1,2})\mathcal{A}_i \ (i \in \{1, 2\}). You may assume that the transition functions δi∈Qi×Σ→Qi (i∈{1,2})\delta_i \in Q_i \times \Sigma \rightarrow Q_i\ (i \in \{1, 2\}) are total functions. Give a non-deterministic automaton that accepts L1⊗L2L_1 \otimes L_2.

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

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

题目描述​

设 Σ\Sigma 为有限字母表，ε\varepsilon 为空串。对 w1,w2∈Σ∗w_1,w_2\in\Sigma^*，递归定义它们的洗牌（shuffle） w1⊗w2⊆Σ∗w_1\otimes w_2\subseteq\Sigma^*：

ε⊗w=w⊗ε={w},\varepsilon\otimes w=w\otimes\varepsilon=\{w\},

且对 a,b∈Σa,b\in\Sigma、w1,w2∈Σ∗w_1,w_2\in\Sigma^*，

(aw1)⊗(bw2)={aw∣w∈w1⊗(bw2)}∪{bw∣w∈(aw1)⊗w2}.(aw_1)\otimes(bw_2) =\{aw\mid w\in w_1\otimes(bw_2)\} \cup \{bw\mid w\in(aw_1)\otimes w_2\}.

对语言 L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^*，定义

L1⊗L2=⋃w1∈L1, w2∈L2w1⊗w2.L_1\otimes L_2 =\bigcup_{w_1\in L_1,\ w_2\in L_2}w_1\otimes w_2.

例如

{ab,ba}⊗{ε,c}={ab,cab,acb,abc,ba,cba,bca,bac}.\{ab,ba\}\otimes\{\varepsilon,c\} =\{ab,cab,acb,abc,ba,cba,bca,bac\}.

回答下列问题。

（1）计算 {a,bb}⊗{ab,cc}\{a,bb\}\otimes\{ab,cc\}。

（2）设 DFA Ai=(Qi,Σ,δi,qi,0,Fi)\mathcal A_i=(Q_i,\Sigma,\delta_i,q_{i,0},F_i) 分别识别语言 Li (i=1,2)L_i\ (i=1,2)，并假定两个转移函数均为全函数。构造一个识别 L1⊗L2L_1\otimes L_2 的 NFA。

（3）证明第（2）问构造的正确性。

（4）令 L3={anbn∣n≥0}L_3=\{a^nb^n\mid n\ge0\}、 L4={cmdm∣m≥0}L_4=\{c^md^m\mid m\ge0\}。证明 L3⊗L4L_3\otimes L_4 不是上下文无关语言。可以使用上下文无关语言泵引理。

Kai​

本页目录