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

标签：

• TITech
• Pumping-Lemma
• Deterministic-Finite-Automaton

Author

GPT-5

Description

アルファベットを とし、次の二つの言語を考える。

(1) が正規言語か否かを判定せよ。正規なら決定性有限オートマトンを示し、正規でないなら反復補題を用いて証明せよ。

(2) についても同様に答えよ。

Kai

(1)

は正規言語ではない。正規であると仮定し、反復長を とする。文字列

を取る。先頭の に が 個あり、 は先頭の 0 の列の末尾に 1 個、その後の各 0 の直後に 個ある。従って両者は 個で、 である。

反復補題による任意の分解 で 、 を満たすものを考える。ある に対して である。 を 2 回反復すると、先頭の 0 の列だけが 文字長くなるため、 は 個になるが は 個のままである。従って となり、反復補題に矛盾する。

(2)

二進文字列では

となる。これは隣接するビットの変化を足し合わせると途中の変化が相殺され、最初と最後のビットだけが残るためである。従って は、空文字列、長さ 1 の文字列、および最初と最後のビットが等しい文字列の集合であり、正規言語である。

次の DFA が を認識する。 は開始状態、二文字の状態名は「最初のビット・現在の末尾ビット」を表す。受理状態は である。