情報数学I 期末レポート

『言語理論とオートマトン』(ISBN4-7819-0250-2)の演習問題を何題か解いてみました。

1. 言語とその表現

1.1 関数 $J\left(xy\right)=\frac{\left(x+y-1\right)\left(x+y-2\right)}{2}+y$ は順序対を整数全体に対応させる。関数K,Lで、次の性質をみたすものを求めよ。
K(J(x,y))=x, L(J(x,y))=y

$L\left(J\left(xy\right)\right)=J\left(xy\right)-\frac{n\left(n+1\right)}{2}$
$K\left(J\left(xy\right)\right)=n+2-L\left(J\left(xy\right)\right)$
ただし、 $\frac{n\left(n+1\right)}{2}<J\left(xy\right)\leqq \frac{\left(n+1\right)\left(n+2\right)}{2}$

1.2 J^ (w,x,y) = J(w, J(x,y))とおく。1000に対応する三つ組(x,y,z)を求めよ。

(36, 1, 4)

1.5 或る整数の集合を、小さい順に列挙する手続きが存在する場合には、その集合は 次の意味で帰納的であることを証明せよ : 与えられた整数が、その集合に属す るか否かを判定するアルゴリズムが存在する。

与えられた整数をnとし、 その集合の要素を小さい順に、nより大きくなるまで列挙する。 nが列挙されれば、nがその集合に属することが確かめられる。 nが列挙されずに手続きが終了すれば、nが集合に属さないことが確かめられる。 また、n以下の整数は高々有限個であり、この手続きは有限時間内に終了する。 したがって、この集合は帰納的である。

1.6 任意の有限集合は帰納的である事を示せ。

有限時間で、要素をすべて列挙することができるので、 すべての要素と比較することで集合に属するか否かを 有限時間で確かめられる。 したがって、帰納的である。

2. 文法

2.1 L = {w|w∈{0,1}^*, wは隣り合う2個の1を含まぬ} を生成する正規文法を示せ

S → ε   S → 1A   A → 0S
S → 0S   S → 1

2.2 L = {w|w∈{a,b}^*, wはbのちょうど2倍のaを含む}を生成する文脈自由文法を示せ

S → ε
S → SS
S → abb   S → aSbb   S → abSb
S → bab   S → bSab   S → baSb
S → bba   S → bSba   S → bbSa

2.4 L = {w|w∈{a,b,c}^*, wは同じ個数のa,b,cを含む}を生成する文脈依存文法を示せ

S→ε   AB→BA  BA→AB  A→a
S→SS   AC→CA  CA→AC  B→b
S→ABC  CB→BC  BC→CB  C→c

2.5 L = {ww|w∈{0,1}^*} を生成する文脈依存文法を示せ。 言い替えれば、Lは{0,1}^*の語で、左半分と右半分とが等しいようなものの全体 の集合である。

S→ε   CB→BC  A→1
S→ACS  DA→AD  B→0
S→BDS  CA→AC  C→1
        DB→BD  D→0

2.7 例2.7の文法Gに対して、以下の語がL(G)に属するか否かを、定理2.2のアル ゴリズムによって決定せよ。
a) abaa b) abbb c) baaba

T_mを、{a,b,c}^*の元で、その長さが5以下であり、 Sから高々mステップで導出できるような列全体の集合と定義する。

T0 = {S}
T1 = T0 ∪ {aAS, a}
T2 = T1 ∪ {aSbAS, abaS, aSSS, aAsAS, aAa}
T3 = T2 ∪ {aSbAa, abaa, aaSS, aSaS, aSSa, aAaAa, aSbAa, abaa, aSSa}
T4 = T3 ∪ {aabAa, aaaS, aaSa, aSaa, aabAa}
T5 = T4 ∪ {aaaa}
T6 = T5 ∪ φ

ゆえに、T₅ = T₆ が、 L(G)の長さが5以下のすべての文字列である。

• a) abaa ∈ L(G)
• b) aabb ¬∈ L(G)
• c) baaba ¬∈ L(G)

2.8 Gが文脈自由文法である場合、定理2.2のmの上限を改良できるか? Gが正規ならばどうか?

文脈自由文法ならば、導出を最左導出に制限する?
正規ならば…

2.9 例2.3の文法Gを考える。以下の語に対するGの導出の木を描け。

a) ababab b) bbbaabaa c) aabbaabb

a) ababab

     S
   ／ ＼
  a     B
      ／ ＼
     b     S
         ／ ＼
        a     B
            ／ ＼
           b     S
               ／ ＼
              a     B
                    |
                    b

b) bbbaabaa

     S
   ／ ＼
  b     A
      ／|＼
     b  A  ＼
      ／|＼  ＼
     b  A  A   ＼
        |  |     A
        a  a   ／|＼
              b  A  A
                 |  |
                 a  a

c) aabbaabb

     S
   ／ ＼
  a     B
      ／|＼
     a  B  B
        |  |＼
        b  b  S
            ／ ＼
           a     B
               ／|＼
              a  B  B
                 |  |
                 b  b

2.10 G={V_N, V_T, P, S}, V_N = {A, B, S}, V_T = {0,1} とする。Pは下記の生成規則の集合であるとする。

S → 0AB   B → 01
B → 0    A1 → SB1
B → SA   A0 → S0B

L(G)が空であることを証明できるか?

証明できる。

記号Sに適用可能な規則は S→0AB だけであり、これは記号Aを導入する。 ところで、Aに適用可能な規則は A1→SB1 と A0→S0B であり、共にSを導入する。 したがって、Sから導出される記号列にはSまたはAが含まれ、 ゆえにGは端記号列を導出しない。

よって、L(G)=φ

2.11 図2.7に、ある文脈自由文法

G={V_N, V_T, P, S}

の導出の木を示した。

この木の結果は何か?

cbbbbcb

どんな記号がV_Nの中になければならないか?

S,A,B

V_Tに属しうるのはどんな記号か?

c,b

小文字が終端記号をあらわすという我々も慣習を抜きにしても、b,cがV_Tに属さなければならないことがいえるか?　それとも、それらはV^Nにも含まれ得るか?

b,cはV_Tではなく、V_Nに属しても良い。

どんな規則がPに属しているか?

P ⊇ {S→AB, A→SS, S→cb, S→b, B→bA, A→BS, B→b}

語bcbbcbbはL(G)に属しているか?

属していない(?)

2.12 GをA→xBおよびA→xという形の規則のみをもつ文法とする。ここでA,Bじゃ一個の変数を表し、xは終端記号列をあらわす。L(G)が、正規文法によって生成できることを示せ。

xの長さが2以上である規則のそれぞれについて以下のように書き換えることで、 等価な正規文法を生成できる。

x = x₁ x₂ x₃ x₄ … x_n と置くと、新たな変数 X₁, X₂, X₃, X₄, …, X_nを導入して、

A→x1X1
X1→x2X2
X2→x3X3
  …
Xn→xnB (もしくは Xn→xn )

等価であることの証明は省略。

3. 有限オートマトンと正規文法

3.1 0の直後(右隣)には必ず1が来るような、{0,1}^*に属する列をすべて受理する一方向性有限オートマトンを作れ。

({q0, q1, q2}, {0,1}, δ, q0, {q0}) δ(q0, 1) = q0 δ(q0, 0) = q1 δ(q1, 1) = q0 δ(q1, 0) = q2 δ(q2, 1) = q2 δ(q2, 0) = q2

3.2 3.1の有限オートマトンから、そこに述べられた言語を生成する3型文法を構成せよ。

({q0, q1, q2}, {0,1}, q0, P)

P: q0 → ε
   q0 → 1q0
   q0 → 0q1
   q1 → 1q0
   q1 → 0q2
   q2 → 1q2
   q2 → 0q2

3.4 M = ({q₀, q₁, q₂}, {a,b}, δ, q₀, {q₂})を次のような非決定性有限オートマトンとする。

δ(q0, a) = {q1, q2}
δ(q1, a) = {q0, q1}
δ(q2, a) = {q0, q2}
δ(q0, b) = {q0}
δ(q1, b) = φ
δ(q2, b) = {q1}

T(M)を受理する決定性有限オートマトンを作れ。

M' = (pow({q₀, q₁, q₂}), {a,b}, δ', {q₀}, {x|x∈pow({q₀, q₁, q₂}), q₂∈x})
δ'(X, i) = {δ(x,i)|x∈X}
具体的な構成は省略。

3.6 非決定性有限オートマトンの概念を用いて、次のことを証明せよ : Lが3型ならば、

L^R = {w|wの記号を逆順に並べたものが、Lに属する}

もまた、3型言語である。

中間レポートで示したように、L^Rを受理する有限オートマトンが存在し、したがってL^Rは3型言語である。

3.9 Lを3型言語とする。Init(L)によって、適当にyをとればxy∈Lとなるような語xの集合をあらわす。Init(L)が3型言語であることを示せ。

Lを受理するオートマトンを M = (S, Σ, δ, q₀, F) と置き、以下のような新しいオートマトンを構成する。

M' = (S, Σ, δ, q0, F')
F' = F ∪ {q | δ*(q,y)∈F}

すると、このオートマトンは明らかに、Init(L)を受理する。 したがって、Init(L)は3型言語。

4. 文脈自由文法

4.3 二つの列α₁,α₂とcfg Gが与えられたとき、α₁ ⇒_G^* α₂ かどうかを判定するアルゴリズムを与えよ

記号列を状態、文法規則の適用を行為とする探索問題として定式化される。ただし、記号列が|α₂|よりも長くなったノードはそれ以上探索する必要はない。

4.5 文法 G = ({S,T,L}, {a,b,+,-,×,/,[,],}, P, S),

P: S→T+S  T→L×T  L→[S]
   S→T-S  T→L/T   L→a
   S→T    T→L     L→b

を考える。L(G)がどんなものか、簡単に説明せよ。L(G)を生成するChomsky標準形文法を示せ。

a,b上の四則演算?

Chomsky標準文法

P: S→TD1
   S→TD2   T→TD2
   S→C3D3  T→C3D3  L→C3D3
   S→α    T→α    L→α
   S→β    T→β    L→β

   C1 → +
   C1 → -
   C2 → ×
   C2 → /
   C3 → [
   C4 → ]

4.6 文法 G = ({A,B,C}, {0,1}, P, A) を考えよう。

P: A→0A1  B→1C0
   A→0AC  B→AC
   A→0    C→1CB
   A→aB0  C→AB

次の条件を満たす等価な文法G₁を見つけよ; もし、DがG₁の変数なら、ある終端記号列wについて、D ⇒^*wとなっている。

BとCからは終端記号列は導出されてないので、
({A}, {0,1}, {A→0A1, A→0}, A)

4.7 GはChomsky標準形文法で、w∈L(G)とし、しかもpステップからなるwの導出が存在するなら、wの長さはどれくらいか?　証明をつけて答えよ。

はじめの記号列は、文記号一個だけからなる記号列であり、長さ1、変数の数1である。

A→BC型の規則によって変数の数が1増え、A→aの形の規則の適用によって変数の数が1減る。最初にある変数は文記号の1個だけであるから、wの導出にはn回のA→BC型の規則と、n+1回のA→a型の規則が使われていることになる。

n+(n+1)=p
      n=(p-1)/2

ところで、A→BC型の規則によって記号列の長さは1増え、A→aの形の規則の適用によっては長さは変化しない。したがって、wの長さは 1+n=(p+1)/2