跳到主要内容

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

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

设 A=(Q,Σ,δ,q0,F)\mathcal A=(Q,\Sigma,\delta,q_0,F) 为 DFA。对 QQ 上的二元关系定义

R0=Q×Q,Rn+1=Φ(Rn),R_0=Q\times Q,\qquad R_{n+1}=\Phi(R_n),

其中

(q,q′)∈Φ(R)  ⟺  {q∈F  ⟺  q′∈F,(δ(q,a),δ(q′,a))∈R(∀a∈Σ).(q,q')\in\Phi(R) \iff \begin{cases} q\in F\iff q'\in F,\\ (\delta(q,a),\delta(q',a))\in R & (\forall a\in\Sigma). \end{cases}

（1）对 Σ={0,1}\Sigma=\{0,1\}、F={q0,q2}F=\{q_0,q_2\} 且转移如下的 DFA，求每个 RnR_n。

状态输入 00输入 11
q0q_0q0q_0q1q_1
q1q_1q1q_1q2q_2
q2q_2q2q_2q1q_1

（2）利用 Φ\Phi 的单调性证明 R0⊇R1⊇R2⊇⋯R_0\supseteq R_1\supseteq R_2\supseteq\cdots。

（3）令 Rω=⋂n∈NRnR_\omega=\bigcap_{n\in\mathbb N}R_n。判断该下降链是否必在有限步内稳定，并证明结论。

（4）将 δ\delta 扩张为 δ∗:Q×Σ∗→Q\delta^*:Q\times\Sigma^*\to Q。证明：若 (q,q′)∈Rn(q,q')\in R_n 且 n≥1n\ge1，则对任意长度为 n−1n-1 的词 ww，

δ∗(q,w)∈F  ⟺  δ∗(q′,w)∈F.\delta^*(q,w)\in F\iff\delta^*(q',w)\in F.

（5）令 q≈q′q\approx q' 表示从两状态出发接受相同语言。证明 Rω⊆≈R_\omega\subseteq\approx。

（6）证明反向包含关系 ≈⊆Rω\approx\subseteq R_\omega。

Kai​

(1)​

R1R_1 只区分“接受态”和“非接受态”，所以

R1={q0,q2}2∪{(q1,q1)}.R_1=\{q_0,q_2\}^2\cup\{(q_1,q_1)\}.

q0,q2q_0,q_2 在输入 00 后仍分别到达 q0,q2q_0,q_2，在输入 11 后都到达 q1q_1，故二者在下一轮仍不被区分。因此

R0=Q2,Rn={q0,q2}2∪{(q1,q1)}(n≥1).\boxed{R_0=Q^2,\qquad R_n=\{q_0,q_2\}^2\cup\{(q_1,q_1)\}\quad(n\ge1).}

(2)​

R1=Φ(R0)⊆R0R_1=\Phi(R_0)\subseteq R_0。若 Rn⊆Rn−1R_n\subseteq R_{n-1}，由 Φ\Phi 单调可得

Rn+1=Φ(Rn)⊆Φ(Rn−1)=Rn.R_{n+1}=\Phi(R_n)\subseteq\Phi(R_{n-1})=R_n.

归纳即得下降链。

(3)​

必在有限步内稳定。因为 Q2Q^2 只有 ∣Q∣2|Q|^2 个有序对；若 Rn+1⊊RnR_{n+1}\subsetneq R_n，至少删除一个有序对。因此严格下降至多发生 ∣Q∣2|Q|^2 次，随后存在 NN 使

RN=RN+1=⋯=Rω.R_N=R_{N+1}=\cdots=R_\omega.

(4)​

对 nn 归纳。n=1n=1 时 w=εw=\varepsilon，结论正是 R1=Φ(R0)R_1=\Phi(R_0) 对接受性的要求。

设命题对 nn 成立。若 (q,q′)∈Rn+1(q,q')\in R_{n+1}，将任意 ∣w∣=n|w|=n 的词写成 w=avw=av。由定义

(δ(q,a),δ(q′,a))∈Rn.(\delta(q,a),\delta(q',a))\in R_n.

再对长度为 n−1n-1 的 vv 使用归纳假设，并利用 δ∗(q,av)=δ∗(δ(q,a),v)\delta^*(q,av)=\delta^*(\delta(q,a),v)，即得结论。

(5)​

若 (q,q′)∈Rω(q,q')\in R_\omega，则它属于每个 RnR_n。对任意词 ww，在（4）中取 n=∣w∣+1n=|w|+1，便有

δ∗(q,w)∈F  ⟺  δ∗(q′,w)∈F.\delta^*(q,w)\in F\iff\delta^*(q',w)\in F.

故 q≈q′q\approx q'，即 Rω⊆≈R_\omega\subseteq\approx。

(6)​

若 q≈q′q\approx q'，取空词可知 q,q′q,q' 的接受性相同；对任意 a∈Σa\in\Sigma 和 w∈Σ∗w\in\Sigma^*，

δ∗(δ(q,a),w)=δ∗(q,aw),\delta^*(\delta(q,a),w)=\delta^*(q,aw),

故 δ(q,a)≈δ(q′,a)\delta(q,a)\approx\delta(q',a)。因此 ≈⊆Φ(≈)\approx\subseteq\Phi(\approx)。

又 ≈⊆R0\approx\subseteq R_0。若 ≈⊆Rn\approx\subseteq R_n，利用单调性得到

≈⊆Φ(≈)⊆Φ(Rn)=Rn+1.\approx\subseteq\Phi(\approx)\subseteq\Phi(R_n)=R_{n+1}.

归纳知 ≈⊆Rn\approx\subseteq R_n 对所有 nn 成立，从而 ≈⊆Rω\approx\subseteq R_\omega。

本页目录