跳到主要内容

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

标签：
留学警示（商务部公告2026年第12号）

根据中华人民共和国商务部公告2026年第12号，东京科学大学（東京科学大学/Institute of Science Tokyo）已被列入关注名单。请中国留学申请者慎重考虑相关政策及其可能带来的影响。

Author​

GPT-5

Description​

Let and let be the set of finite strings over . For , define decorated replacement relations by

  • iff is obtained from by replacing all occurrences of by ;
  • iff is obtained by replacing some (possibly zero) occurrences of by .

Define and when the corresponding relation holds for some .

(1) Let , , and . Given , find such that .

(2) Show that is transitive.

(3) Show that is not transitive.

(4) Show that is antisymmetric.

(5) Show that is not antisymmetric.

Kai​

(1)​

の 2 個の を同じ文字列で置換する必要がある。実際、

なので

(2)​

を , , で定まる準同型とする。 かつ なら、ある に対して

である。合成すると

となるので である。よって は推移的である。

(3)​

次が反例である。

一方、 から 1 回で得られる文字列は 、、、 のいずれかである。 はそのどれにもならないため、 である。したがって推移的ではない。

(4)​

かつ とする。 に がなければ置換で変化しないので である。

に含まれる の個数を 、置換語 に含まれる の個数を とする。逆向きの置換語 に含まれる の個数を とすれば、 の個数を比較して

であるから である。また

なので両辺の増分は非負であり、和が 0 になるには が必要である。 はそれぞれ 1 個の を含む長さ 1 の語、すなわち である。したがって であり、 は反対称的である。

(5)​

が成り立つが、 である。よって は反対称的ではない。

目录