東京工業大学 情報理工学院 数理・計算科学系 2016年8月実施 午前 問C
Author
祭音Myyura (co-authored with GPT 5.6 SOL)
Description
Σ={a,b,c} とし、その文字からなる有限列全体を Σ∗ とする。ω∈Σ∗ に対し、次の二項関係を定める。
- α⟼(ω)β：α 中のすべての a を ω に置き換えると β になる。
- α⇝(ω)β：α 中のいくつかの a（0 個でもよい）を ω に置き換えると β になる。
たとえば、次が成り立つ。
abaabbabaabbabaabbabaabbabaabbabaabbabaabbccc⟼(cac)cacbcaccacbb,⇝(cac)cacbcaccacbb,⇝(cac)abcacabb,⇝(cac)abaabb,⟼(a)abaabb,⟼(ε)bbb,⇝(ε)abbb,⟼(abc)ccc.
ε は空列を表す。ある ω に対してそれぞれの関係が成立するとき、α↦β、α⇝β と書く。
(1) α=abac、β=caabcaac、γ=cbababcbabac とする。
α⟼(caa)β⟼(ba)γ のとき、α⟼(ω)γ となる ω を書け。
(2) ↦ が推移的であることを示せ。
(3) ⇝ が推移的でないことを示せ。
(4) ↦ が反対称的であることを示せ。
(5) ⇝ が反対称的でないことを示せ。
（注）集合 X 上の二項関係 R が推移的であるとは、任意の x,y,z∈X に対して、xRy かつ yRz ならば xRz が成り立つことである。また、反対称的であるとは、任意の x,y∈X に対して、xRy かつ yRx ならば x=y が成り立つことである。
题目描述
令 Σ={a,b,c}，以 Σ∗ 表示字母表 Σ 上的全体有限字符串。对 ω∈Σ∗，定义带标记的替换关系：
- α⟼(ω)β 当且仅当 β 是把 α 中出现的每一个 a 都替换为 ω 所得的字符串；
- α⇝(ω)β 当且仅当 β 是把 α 中出现的某些 a（允许一个也不替换）替换为 ω 所得的字符串。
上列八个替换示例同样适用于这里的定义，其中 ε 表示空串。
若对某个 ω∈Σ∗ 相应的带标记关系成立，则分别记为 α↦β 和 α⇝β。回答：
-
令
α=abac,β=caabcaac,γ=cbababcbabac.
已知
α⟼(caa)β⟼(ba)γ,
求使 α⟼(ω)γ 成立的 ω。
-
证明关系 ↦ 具有传递性。
-
证明关系 ⇝ 不具有传递性。
-
证明关系 ↦ 具有反对称性。
-
证明关系 ⇝ 不具有反对称性。
注：关系 R 具有传递性，是指对任意 x,y,z∈X，由 xRy 且 yRz 可推出 xRz；关系 R 具有反对称性，是指对任意 x,y∈X，由 xRy 且 yRx 可推出 x=y。
Kai
(1)
α=abac の 2 個の a を同じ文字列で置換する必要がある。実際、
cbababcbabac=cbababcbabac
なので
ω=cbaba.
(2)
Hu:Σ∗→Σ∗ を Hu(a)=u, Hu(b)=b, Hu(c)=c で定まる準同型とする。α↦β かつ β↦γ なら、ある u,v に対して
β=Hu(α),γ=Hv(β)
である。合成すると
γ=Hv(Hu(α))=HHv(u)(α)
となるので α↦γ である。よって ↦ は推移的である。
(3)
次が反例である。
aa⇝(b)ba⇝(c)bc.
一方、aa から 1 回で得られる文字列は aa、ωa、aω、ωω のいずれかである。bc はそのどれにもならないため、aa⇝bc である。したがって推移的ではない。
(4)
α↦β かつ β↦α とする。α に a がなければ置換で変化しないので α=β である。
α に含まれる a の個数を p>0、置換語 u に含まれる a の個数を r とする。逆向きの置換語 v に含まれる a の個数を s とすれば、a の個数を比較して
であるから r=s=1 である。また
∣β∣=∣α∣+p(∣u∣−1),∣α∣=∣β∣+p(∣v∣−1).
∣u∣,∣v∣≥1 なので両辺の増分は非負であり、和が 0 になるには ∣u∣=∣v∣=1 が必要である。u,v はそれぞれ 1 個の a を含む長さ 1 の語、すなわち u=v=a である。したがって α=β であり、↦ は反対称的である。
(5)
aa⇝(aa)aaa,aaa⇝(ε)aa
が成り立つが、aa=aaa である。よって ⇝ は反対称的ではない。