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

标签：

• TITech
• Binary-Relations

Author

GPT-5

Description

Let $\Sigma=\{\mathtt a,\mathtt b,\mathtt c\}$ and let $\Sigma^*$ be the set of finite strings over $\Sigma$. For $\omega\in\Sigma^*$, define decorated replacement relations by

• $\alpha\overset{(\omega)}{\longmapsto}\beta$ iff $\beta$ is obtained from $\alpha$ by replacing all occurrences of $\mathtt a$ by $\omega$;
• $\alpha\overset{(\omega)}{\rightsquigarrow}\beta$ iff $\beta$ is obtained by replacing some (possibly zero) occurrences of $\mathtt a$ by $\omega$.

Define $\alpha\mapsto\beta$ and $\alpha\rightsquigarrow\beta$ when the corresponding relation holds for some $\omega\in\Sigma^*$.

(1) Let $\alpha=\mathtt{abac}$, $\beta=\mathtt{caabcaac}$, and $\gamma=\mathtt{cbababcbabac}$. Given $\alpha\overset{(\mathtt{caa})}{\longmapsto}\beta\overset{(\mathtt{ba})}{\longmapsto}\gamma$, find $\omega$ such that $\alpha\overset{(\omega)}{\longmapsto}\gamma$.

(2) Show that $\mapsto$ is transitive.

(3) Show that $\rightsquigarrow$ is not transitive.

(4) Show that $\mapsto$ is antisymmetric.

(5) Show that $\rightsquigarrow$ is not antisymmetric.

题目描述

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

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

若对某个 $\omega\in\Sigma^*$ 相应的带标记关系成立，则分别记为 $\alpha\mapsto\beta$ 和 $\alpha\rightsquigarrow\beta$。回答：

1. 令

   $$\alpha=\mathtt{abac},\qquad \beta=\mathtt{caabcaac},\qquad \gamma=\mathtt{cbababcbabac}.$$

   已知

   $$\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)

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

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

なので

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

(2)

$H_u:\Sigma^*\to\Sigma^*$ を $H_u(\mathtt a)=u$, $H_u(\mathtt b)=\mathtt b$, $H_u(\mathtt c)=\mathtt c$ で定まる準同型とする。$\alpha\mapsto\beta$ かつ $\beta\mapsto\gamma$ なら、ある $u,v$ に対して

$$\beta=H_u(\alpha),\qquad \gamma=H_v(\beta)$$

である。合成すると

$$\gamma=H_v(H_u(\alpha))=H_{H_v(u)}(\alpha)$$

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

(3)

次が反例である。

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

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

(4)

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

$\alpha$ に含まれる $\mathtt a$ の個数を $p>0$、置換語 $u$ に含まれる $\mathtt a$ の個数を $r$ とする。逆向きの置換語 $v$ に含まれる $\mathtt a$ の個数を $s$ とすれば、$\mathtt a$ の個数を比較して

$$p=prs$$

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

$$|\beta|=|\alpha|+p(|u|-1), \qquad |\alpha|=|\beta|+p(|v|-1).$$

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

(5)

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

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