跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2016年8月実施 午前 問C

标签：

Author​

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

Description​

Σ={a,b,c}\Sigma=\{\mathtt a,\mathtt b,\mathtt c\} とし、その文字からなる有限列全体を Σ∗\Sigma^* とする。ω∈Σ∗\omega\in\Sigma^* に対し、次の二項関係を定める。

  • α⟼(ω)β\alpha\overset{(\omega)}{\longmapsto}\beta：α\alpha 中のすべての a\mathtt a を ω\omega に置き換えると β\beta になる。
  • α⇝(ω)β\alpha\overset{(\omega)}{\rightsquigarrow}\beta：α\alpha 中のいくつかの a\mathtt a（00 個でもよい）を ω\omega に置き換えると β\beta になる。

ε\varepsilon は空列を表す。ある ω\omega に対してそれぞれの関係が成立するとき、α↦β\alpha\mapsto\beta、α⇝β\alpha\rightsquigarrow\beta と書く。

(1) α=abac\alpha=\mathtt{abac}、β=caabcaac\beta=\mathtt{caabcaac}、γ=cbababcbabac\gamma=\mathtt{cbababcbabac} とする。 α⟼(caa)β⟼(ba)γ\alpha\overset{(\mathtt{caa})}{\longmapsto}\beta\overset{(\mathtt{ba})}{\longmapsto}\gamma のとき、α⟼(ω)γ\alpha\overset{(\omega)}{\longmapsto}\gamma となる ω\omega を書け。

(2) ↦\mapsto が推移的であることを示せ。

(3) ⇝\rightsquigarrow が推移的でないことを示せ。

(4) ↦\mapsto が反対称的であることを示せ。

(5) ⇝\rightsquigarrow が反対称的でないことを示せ。

题目描述​

令 Σ={a,b,c}\Sigma=\{\mathtt a,\mathtt b,\mathtt c\}，以 Σ∗\Sigma^* 表示字母表 Σ\Sigma 上的全体有限字符串。对 ω∈Σ∗\omega\in\Sigma^*，定义带标记的替换关系：

  • α⟼(ω)β\alpha\overset{(\omega)}{\longmapsto}\beta 当且仅当 β\beta 是把 α\alpha 中出现的每一个 a\mathtt a 都替换为 ω\omega 所得的字符串；
  • α⇝(ω)β\alpha\overset{(\omega)}{\rightsquigarrow}\beta 当且仅当 β\beta 是把 α\alpha 中出现的某些 a\mathtt a（允许一个也不替换）替换为 ω\omega 所得的字符串。

若对某个 ω∈Σ∗\omega\in\Sigma^* 相应的带标记关系成立，则分别记为 α↦β\alpha\mapsto\beta 和 α⇝β\alpha\rightsquigarrow\beta。回答：

  1. 令

    α=abac,β=caabcaac,γ=cbababcbabac.\alpha=\mathtt{abac},\qquad \beta=\mathtt{caabcaac},\qquad \gamma=\mathtt{cbababcbabac}.

    已知

    α⟼(caa)β⟼(ba)γ,\alpha\overset{(\mathtt{caa})}{\longmapsto}\beta \overset{(\mathtt{ba})}{\longmapsto}\gamma,

    求使 α⟼(ω)γ\alpha\overset{(\omega)}{\longmapsto}\gamma 成立的 ω\omega。

  2. 证明关系 ↦\mapsto 具有传递性。

  3. 证明关系 ⇝\rightsquigarrow 不具有传递性。

  4. 证明关系 ↦\mapsto 具有反对称性。

  5. 证明关系 ⇝\rightsquigarrow 不具有反对称性。

Kai​

(1)​

α=abac\alpha=\mathtt a\mathtt b\mathtt a\mathtt c の 2 個の a\mathtt a を同じ文字列で置換する必要がある。実際、

cbaba b cbaba c=cbababcbabac\mathtt{cbaba}\,\mathtt b\,\mathtt{cbaba}\,\mathtt c =\mathtt{cbababcbabac}

なので

ω=cbaba.\boxed{\omega=\mathtt{cbaba}}.

(2)​

Hu:Σ∗→Σ∗H_u:\Sigma^*\to\Sigma^* を Hu(a)=uH_u(\mathtt a)=u, Hu(b)=bH_u(\mathtt b)=\mathtt b, Hu(c)=cH_u(\mathtt c)=\mathtt c で定まる準同型とする。α↦β\alpha\mapsto\beta かつ β↦γ\beta\mapsto\gamma なら、ある u,vu,v に対して

β=Hu(α),γ=Hv(β)\beta=H_u(\alpha),\qquad \gamma=H_v(\beta)

である。合成すると

γ=Hv(Hu(α))=HHv(u)(α)\gamma=H_v(H_u(\alpha))=H_{H_v(u)}(\alpha)

となるので α↦γ\alpha\mapsto\gamma である。よって ↦\mapsto は推移的である。

(3)​

次が反例である。

aa⇝(b)ba⇝(c)bc.\mathtt{aa}\overset{(\mathtt b)}{\rightsquigarrow}\mathtt{ba} \overset{(\mathtt c)}{\rightsquigarrow}\mathtt{bc}.

一方、aa\mathtt{aa} から 1 回で得られる文字列は aa\mathtt{aa}、ωa\omega\mathtt a、aω\mathtt a\omega、ωω\omega\omega のいずれかである。bc\mathtt{bc} はそのどれにもならないため、aa⇝̸bc\mathtt{aa}\not\rightsquigarrow\mathtt{bc} である。したがって推移的ではない。

(4)​

α↦β\alpha\mapsto\beta かつ β↦α\beta\mapsto\alpha とする。α\alpha に a\mathtt a がなければ置換で変化しないので α=β\alpha=\beta である。

α\alpha に含まれる a\mathtt a の個数を p>0p>0、置換語 uu に含まれる a\mathtt a の個数を rr とする。逆向きの置換語 vv に含まれる a\mathtt a の個数を ss とすれば、a\mathtt a の個数を比較して

p=prsp=prs

であるから r=s=1r=s=1 である。また

∣β∣=∣α∣+p(∣u∣−1),∣α∣=∣β∣+p(∣v∣−1).|\beta|=|\alpha|+p(|u|-1), \qquad |\alpha|=|\beta|+p(|v|-1).

∣u∣,∣v∣≥1|u|,|v|\geq1 なので両辺の増分は非負であり、和が 0 になるには ∣u∣=∣v∣=1|u|=|v|=1 が必要である。u,vu,v はそれぞれ 1 個の a\mathtt a を含む長さ 1 の語、すなわち u=v=au=v=\mathtt a である。したがって α=β\alpha=\beta であり、↦\mapsto は反対称的である。

(5)​

aa⇝(aa)aaa,aaa⇝(ε)aa\mathtt{aa}\overset{(\mathtt{aa})}{\rightsquigarrow}\mathtt{aaa}, \qquad \mathtt{aaa}\overset{(\varepsilon)}{\rightsquigarrow}\mathtt{aa}

が成り立つが、aa≠aaa\mathtt{aa}\neq\mathtt{aaa} である。よって ⇝\rightsquigarrow は反対称的ではない。

本页目录