跳到主要内容

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

标签：

Author​

GPT-5

Description​

アルファベットを {0,1}\{0,1\} とし、次の二つの言語を考える。

L1={w∣w に含まれる部分文字列 01 と 00 の個数が等しい},L_1=\{w\mid w\text{ に含まれる部分文字列 }01\text{ と }00\text{ の個数が等しい}\},
L2={w∣w に含まれる部分文字列 01 と 10 の個数が等しい}.L_2=\{w\mid w\text{ に含まれる部分文字列 }01\text{ と }10\text{ の個数が等しい}\}.

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

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

题目描述​

字母表为 {0,1}\{0,1\}，考虑两个语言

L1={w∣w 中子串 01 与 00 的出现次数相等},L_1=\{w\mid w\text{ 中子串 }01\text{ 与 }00\text{ 的出现次数相等}\},
L2={w∣w 中子串 01 与 10 的出现次数相等}.L_2=\{w\mid w\text{ 中子串 }01\text{ 与 }10\text{ 的出现次数相等}\}.

这里子串按字符串中的相邻位置计数。

  1. 判断 L1L_1 是否为正则语言。若是，给出识别它的确定有限自动机；若不是，使用抽引引理证明。
  2. 对 L2L_2 作同样判断：若为正则语言则给出确定有限自动机，否则使用抽引引理证明。

考点​

  • 子串出现次数的不变量：分析相邻二进制位的转移如何改变 0101、0000、1010 的计数差。
  • 正则语言抽引引理：若计数相等需要无界记忆，则选取适当长串并证明抽引会破坏等式。
  • 确定有限自动机构造：若计数差可由首尾字符等有限信息决定，则设计状态记录所需边界信息。

Kai​

(1)​

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

s=0p(10)p−21s=0^p(10)^{p-2}1

を取る。先頭の 0p0^p に 0000 が p−1p-1 個あり、0101 は先頭の 0 の列の末尾に 1 個、その後の各 0 の直後に p−2p-2 個ある。従って両者は p−1p-1 個で、s∈L1s\in L_1 である。

反復補題による任意の分解 s=xyzs=xyz で ∣xy∣≤p|xy|\leq p、∣y∣>0|y|>0 を満たすものを考える。ある r≥1r\geq1 に対して y=0ry=0^r である。yy を 2 回反復すると、先頭の 0 の列だけが rr 文字長くなるため、0000 は p+r−1p+r-1 個になるが 0101 は p−1p-1 個のままである。従って xy2z∉L1xy^2z\notin L_1 となり、反復補題に矛盾する。

(2)​

二進文字列では

#01(w)−#10(w)={1,w が 0 で始まり 1 で終わる,−1,w が 1 で始まり 0 で終わる,0,それ以外\#_{01}(w)-\#_{10}(w) =\begin{cases} 1,&w\text{ が }0\text{ で始まり }1\text{ で終わる},\\ -1,&w\text{ が }1\text{ で始まり }0\text{ で終わる},\\ 0,&\text{それ以外} \end{cases}

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

次の DFA が L2L_2 を認識する。qsq_s は開始状態、二文字の状態名は「最初のビット・現在の末尾ビット」を表す。受理状態は qs,q00,q11q_s,q_{00},q_{11} である。

本页目录