形式言語理論まとめ

用語

閉包

要するに$$L{**}$$と$$L{+}$$

Kleene閉包

$$L^{**}$$

有限オートマトン

$$\epsilon$$動作付非決定性有限オートマトン$$->$$決定性有限オートマトン

pumping lemma

内容

正則言語は、ある有限の定数N(実は状態数以下)があって、$$uvw\in L$$のとき、$$1\leq |v| < N$$であって、$$m\geq 0$$に対し、$$uv^mw\in L$$

証明の概略

オートマトンの状態数をNとおくと、$$n>=N$$なので、
$$p_0 \stackrel{a_1}{\rightarrow} p_1 \stackrel{a_2}{\rightarrow} ... \stackrel{a_n}{\rightarrow} p_n$$
に対して、この列の中には、必ず同じ状態が含まれ、$$p_i=p_j$$と置くことができる。uは繰り返しの前の部分の文字列$$a_1...a_i$$,vは中$$a_{i+1}...a_{j}$$,wは後ろ$$a_{j+1}...a_n$$とおく。繰り返しの部分はいくら繰り返してもいいので、$$uv^{m}w$$も受理する。
証明から分かるように、これはN以下の部分列に対して適用できることが分かる。mが0も含むことに注意
このことから、正則言語は、少なくとも長さが等差数列になるような記号列の集合の和であることが分かる。

使い方

ある言語が正則でないことを示すのに背理法に使われることが多い。そのまま使ってもいいが、式が複雑になった場合は、証明のやり方に戻ったほうが楽な場合がある。

解答例

背理法を使う。これを受理するオートマトンがあったとする。

pumping lemmaより、ある$$N>=1$$が存在して、長さN以上の$$x \in L$$に対し、$$x=uvw$$と分解でき、($$1<=|v| < N$$)
$$uv^{m}w \in L$$となる。

$$x=0N1N$$を考える。

  • (i)$$v \in 0^{**}$$のとき
    • $$uv2w = 0{N+|v|}1^{N} \notin L$$

    (ii)$$v \in 1^{**}$$のとき
    • $$uv2w = 0{N}1^{N+|v|} \notin L$$

    (iii) $$v \in 0{**}1{**}$$のとき

    • $$v=0{i}1{|v|-i}$$とおいて、
      $$uv2w = 0{N}1{|v|-i}0{i}1^{N} \notin L$$

(i)--(iii)より、これはpumping lemmaと矛盾する。よって、背理法より与題が示された。

解答例2

背理法を使う。これを受理するオートマトンがあったとする。そのオートマトンの状態数をNとおく。このオートマトンは記号列$$0N1N$$を受理するので、

$$p_0 \stackrel{0}{\rightarrow} p_1 \stackrel{0}{\rightarrow} ... \stackrel{0}{\rightarrow} p_N \stackrel{1}{\rightarrow} p_{N+1} ... \stackrel{1}{\rightarrow} p_{2N} $$

という受理計算が存在する。

このとき、状態はN個しかないため、$$p_0,p_1,...,p_N$$の中には同じ状態がある、即ち、ある$$0<=i < j<=N$$が存在して、$$p_i=p_j$$。

よって、この間については、記号列を繰り返しても受理するので、記号列$$0{i}(0{j-i}){2}0{N-j}1N=0{N+(j-i)}1^{N}$$も受理することになる。

これはこのオートマトンがLを受理することと矛盾する。よって、背理法より与題が示された。

解答例

背理法を使う。これを受理するオートマトンがあったとする。そのオートマトンの状態数をNとおく。このオートマトンは記号列$$0N10N1$$を受理するので、

$$p_0 \stackrel{0}{\rightarrow} p_1 \stackrel{0}{\rightarrow} ... \stackrel{0}{\rightarrow} p_N \stackrel{1}{\rightarrow} p_{N+1} \stackrel{0}{\rightarrow} p_{N+2} \stackrel{0}{\rightarrow} ... \stackrel{0}{\rightarrow} p_{2N+1} \stackrel{1}{\rightarrow} p_{2N+2} $$

という受理計算が存在する。

このとき、状態はN個しかないため、$$p_0,p_1,...,p_N$$の中には同じ状態がある、即ち、ある$$0<=i < j<=N$$が存在して、$$p_i=p_j$$。

よって、この間については、記号列を繰り返しても受理するので、記号列$$0{i}(0{j-i}){2}0{N-j}1 0N1=0{N+(j-i)}1 0^N1$$も受理することになる。

これはこのオートマトンがLを受理することと矛盾する。よって、背理法より与題が示された。

解答例

背理法を使う。これを受理するオートマトンがあったとする。

pumping lemmaより、ある$$N>=1$$が存在して、長さN以上の$$x \in L$$に対し、$$x=uvw$$と分解でき、($$1<=|v| < N$$)
$$uv^{m}w \in L (m>=0)$$となる。

$$x=0{N2}$$を考える。

$$|v|=j$$とおく。

$$uv{0}w=0{N2-j},uv{1}w=0{N2},uv{2}w=0{N2+j},uv{3}w=0{N2+2j}... \in L$$とならなくてはならないが、これらは等差数列で、全て平方数となることはないため、矛盾。

よって、背理法より与題が示された。

オートマトンの最小化

最小形

最小化アルゴリズム

ブール行列

文脈自由文法

文脈自由文法:G=(V,T,P,S)

導出木

導出の過程を表した木

文は葉で表され、葉でない親は、導出の過程で置き換えられた変数

Chomsky標準形

単一生成規則も$$\epsilon$$生成規則もない文脈自由文法は、

pumping lemma(uvwxy定理)

N以上の長さの記号列z=uvwxyと分解できて、($$|vx|>=1,|vwx|<=N$$)$$uvnwxny\in L$$

Chomsky標準形に持っていって、$$2^|V|$$の長さ以上の記号列を導出する2分木に$$|V|$$以上の長さの導出の過程があることを言い、そこで変数が重複することから、繰り返せると持っていく。

文脈自由文法の所属判定問題

記号列$$x_1x_2...x_n$$が文脈自由文法G=(V,T,P,S)(Chomsky標準形)から生成されるかどうかを判定するアルゴリズム

(教科書のとは添え字の順番が逆)

for i=1...n{
 V[1][i]=(x[i]を導出する直前の変数の集合)
}
for i=2...n{
 for j=1...n-i-1{
  v[i][j]=\phi //空集合で初期化
  for k=1...j-1{
   V[i][j]に、「生成規則のうち、 V[i][k] * V[i-k][j+k] を並べたものを導出する直前の変数の集合」を追加
  }
 }
}

形式言語理論/形式言語理論まとめ (last edited 2009-03-06 13:30:00 by xyx)