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

标签：

• TITech
• Pumping-Lemma
• Context-Free-Grammar
• Deterministic-Finite-Automaton

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

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

Author

GPT-5

Description

Let

(1) Let be the language of strings whose upper-row string is a palindrome; . Show using the pumping lemma that is not regular.

(2) Give a context-free grammar generating .

(3) Regard each row as a binary number whose leftmost position is the most significant bit, and let consist of strings whose lower row is three times the upper row; . Let . Give a four-state deterministic finite automaton recognizing .

Kai

以下では列記号 を単に と書く。第 1 ビットが上段、第 2 ビットが下段である。

(1)

が正則で、ポンピング長が であると仮定する。文字列

を取る。これは上段が なので に属する。任意の分解 で , を満たすものを考えると、 である。

として を除くと、上段は となり回文ではない。したがって であり、ポンピング補題に矛盾する。よって

(2)

非終端記号を 、開始記号を とし、次の生成規則を取る。

は上段ビット 0、 は上段ビット 1 の任意の列を生成する。 と は同じ上段ビットを両端に付け、下段ビットは左右で独立に選べる。したがってこの文法は、上段が回文で下段が任意の文字列をちょうど生成する。

(3)

では最下位ビットから順に読むことになる。3 倍算の現在の桁への繰上がりを 、入力列を とすると、遷移条件は

到達し得る繰上がりは であり、これらに不正入力用のデッド状態を加えれば 4 状態になる。 を繰上がり の状態、 をデッド状態とする。

初期状態かつ唯一の受理状態は である。入力を読み終えたとき繰上がりが 0 であることが、同じ桁数の下段が上段のちょうど 3 倍であることに対応する。 を受理状態にすることで空文字列も受理される。