今日の予定前回の復習：文脈自由文法プッシュダウンオートマトン

2015/7/15
今日の予定
• 前回の復習
– 文脈自由文法
– プッシュダウンオートマトン
離散システム論
オートマトンと形式言語論(4)
知能システム科学
新田克己
•
•
•
•
•
文脈自由文法とプッシュダウンオートマトン（続）
文脈依存文法
チューリングマシン
Chomskyの階層
計算量、決定可能性
文脈自由文法
(Context Free Grammar)
• A → β A ∈VN, β∈V+
例） A → aBCBde
前回の復習：
文脈自由文法
プッシュダウンオートマトン
プッシュダウンオートマトン
（PDA)（その１）
• 文脈自由言語を受理する
• Chomsky標準形
A→BC あるいは A→a
• Greibach標準形
A→aα (αは非終端記号列，空でも良い）
プッシュダウンオートマトン
（その３）
M=<K，Σ，Γ，P，q0，z0，F＞
K:内部状態の集合
Σ：入力記号の集合
Γ：スタック上に置く記号の集合
q0：初期状態（q0∈K)
z0：スタック上の初期記号（z0∈Γ）
F:最終状態の集合（F⊂K)
P:状態推移関数δの集合
1
2015/7/15
たとえば
K={q0,q1,q2}
Σ={0,1} Γ={z0,A}
F＝{q2}
P: δ(q0,0,z0)={(q0,Az0)}
δ(q0,0,A)={(q0,AA)}
δ(q0,1,A)={(q1,λ)}
δ(q1,1,A)={(q1,λ)}
δ(q1, λ, z0)={(q2,λ)}
（続き)
qo
0,Z0/ AZ0
0,A/AA
1, A/ λ
q1
1, A/ λ
λ, Z0/ λ
• このPDAは{0n1n|n=1,2,…}を受理する．
• 一方，00101…のような入力記号列は受理し
ない．
• ある状態から推移できなくなった時点で，入
力記号列は受理できないとして棄却される．
q2
文脈自由文法に対応するPDA
（その１）
文脈自由文法
プッシュダウンオートマトン（続）
• Greibach標準形（ A→aγi ）の文脈自由文法に
対応するPDA
文法G=＜VN，VT，P，σ＞
PDA M=＜K，VT，VN，P’，q１，σ，φ＞
K=｛q１｝
P’: δ(q１,a, A)={(q1,γ１)，‥(q1,γn)}
for A→aγi (i=1,…n) ∈ P
文脈自由文法に対応するPDA
（その２）
• 一般の文脈自由文法( A→α )に対応するPDA
文法G=＜VN，VT，P，S＞
PDA M=＜K, VT，Γ，P’，S，Z，F＞
K={ s, t, f }
Γ=VN∪VT∪{Z}
F=｛f｝
(続き)
P’：
(１)δ(s, ε, Z)={(t,SZ)} SをPDテープに
(２)各A∈VNに対して，
δ(t,ε,A)={(t,α)|A→α∈P}
AがPDテープにあればαに置き換え
(３)各a∈VTに対して，
δ(t,a,a)={(t,ε)}
入力記号とPDテープが同じであれば打ち消し
(４) δ(t,ε,Z)={(f,Z)}
入力記号がなくなり、PDテープが空なら終わり
2
2015/7/15
たとえば
• 文法G=<VN, VT, P, δ>
VN={I,E}, VT={a,b,0,1,(,),+,*}, δ=E
P: I → a|b|Ia|Ib|I0|I1
E → I | E*E | E+E | (E)
{ a,b,aa,ab,a0,a1,aaa,aab,.....,
a*a, a+a, (a), a*b, a+b, ((a)),... }
演習
１．次の文法に対応するプッシュダウンオートマ
トンを作成してください。
VT = {a,b}
VN= {S,A}
s=S
P: S → aAA
A → aS | bS | a
(続き)
• PDA M=<K,Σ,Γ,δ,q0,Z0,F>
K={s,t,f}, Σ=VT={a,b,0,1,(,),+,*}, Γ=VT∪VN∪{Z0}∪{S},
q0=s, F={f}
δ：
δ(s,ε,Z0)={(t,EZ0)}
δ(t,ε,I) = {(t,a), (t,b), (t,Ia), (t,Ib), (t,I0),(t,I1)}
δ(t,ε,E) = {(t,I), (t,E+E), (t,E*E), (t,(E))}
δ(t,a,a) = {(t,ε)}, δ(t,b,b)={(t,ε)}
δ(t,0,0) = {(t,ε)}, δ(t,1,1)={(t,ε)}
δ(t,(,() = {(t,ε)}, δ(t,),))={(t,ε)}
δ(t,+,+) = {(t,ε)}, δ(t,*,*)={(t,ε)}
δ(t,ε,Z0)={(f,Z0)}
PDAに対応する文脈自由文法
（その１）
PDA M=<K，Σ，Γ，P，q0，z0，φ＞
G=＜VN，Σ，P’，σ＞
VN={σ}∪{[p,X,q]|p,q∈K,X∈Γ}
P’：
(１)σ→[q0,z0,q] for all q∈K
PDAに対応する文脈自由文法
（その２）
たとえば
(２)δ(q，a, A)={…, (q1,B1…Bm), …)のとき
[q,A,p]→a[q1,B1,q2] [q2,B2,q3]…
[qm‐1,Bm‐1,qm][qm,Bm,p]
for all qi, p∈K
m=0の場合
δ(q，a, A)={…, (q1,λ), …)であり，
[q,A,q１]→a
e,Z/ε
i,Z/ZZ
• PDA P = (K, Σ, Γ, δ, q0,Z,F)
K={q}, Σ={i,e}, Γ={Z}, q0=q q
δ： δ(q,i,Z)={(q,ZZ)}
δ(q,e,Z)={(q,ε)}
• 文法G=(VT,VN,P,S)
VT= {i,e}, VN={S}, P: S→[qZq]
S→A
[qZq]→i[qZq][qZq]
A→iAA
[qZq]→e A→e
3
2015/7/15
たとえば
たとえば
• PDA P = (K, Σ, Γ, δ, q0,Z,F)
K={p,q}, Σ={a,b,c}, Γ={S,A,B}, q0=p, Z=S, F=Φ
• PDA P = (K, Σ, Γ, δ, q0,Z,F)
K={p,q}, Σ={a,b,c}, Γ={S,A,B}, q0=p, Z=S, F=Φ
δ：
δ(p,a,S)={(p,A)} δ(p,b,A)={(p,ε)} δ(p,c,A)={(q,ε)} δ(p,a,A)={(p,AB)} Δ：
S→[pSp], S→[qSq]
δ(p,a,S)={(p,A)} [pSp]→a[pAp], [pSp]→a[pAq]
δ(p,b,A)={(p,ε)} [pAp]→b
δ(p,c,A)={(q,ε)} [pAq]→c
δ(p,a,A)={(p,AB)} [pAp]→a[pAp][pBp],[pAq]→a[pAq][qBq]
[pAp]→a[pAq][qBp],[pAq]→a[pAp][pBq]
δ(p,b,B)={(p,ε)} [pBp]→b
δ(p,c,B)={(q,ε)} [qBq]→c
δ(p,b,B)={(p,ε)} δ(p,c,B)={(q,ε)} 言語{anbncn}
• 文脈自由文法で記述可能？ No
• 文脈依存文法
σ
VN={σ,B,C}, VT={a,b,c} P: σ→ aσBC σ→aBC
aσBC
CB→BC aaσBCBC
aB→ab bB→bb
aaaBCBCBC
bC→bc cC→cc
aaaBBCCBC
...
aaabbbccc
自然言語は？
文脈依存文法
(Context Sensitive Grammar)
• α→β ｜α｜≦｜β｜
• α１Ａα２→α１βα２
Ａ∈ＶＮ，β∈Ｖ＋，α１，α２∈Ｖ＊
参考
句構造文法
α→β
置き換え規則の制約は
「αには少なくとも１つの非終端記号を含むこと」
のみ。
チューリング機械（TM)
• 自然言語は，文脈自由文法と文脈依存文法
の間に位置すると言われる．
• しかし，計算機上での効率を考慮して，文脈
自由文法で記述することが多い．
4
2015/7/15
チューリング機械の形式的定義
• チューリング機械
M:＜K，Γ，Σ，q0，F，δ＞
K:状態の有限集合
Γ：テープ記号の有限集合，空白は＃
Σ：入力記号の集合，＃以外のΓの部分集合
q0：初期状態
F:最終状態集合
δ：K×Γ → K×（Γｰ{#})×{L,R}
チューリングマシン
チューリング機械（続き）
• テープは無限長で，読み書き可能．
• テープヘッドは左右に移動可能．
• 入力を認識できない場合停止しないこともあ
りうる．
• 0型言語に属さない言語を認識しようとした場
合，「属さない」ことを認識してはくれない．
線形拘束オートマトン
• テープの長さが入力文の長さに比例（線形）
した長さに制限された非決定性のチューリン
グ機械．
チョムスキーの階層
チョムスキーの階層（続き)
0．チューリング機械(Turing Machine)
句構造文法(Phrase Structure Grammar): 0型言語
1. 線形拘束オートマトン(Linear Bounded Automaton)
文脈依存文法(Context Sensitive Grammar)：１型言語
2. プッシュダウンオートマトン(Pushdown Automaton)
文脈自由文法（Context Free Grammar)：２型言語
3．有限オートマトン(Finite Automaton)
正規文法(Regular Grammar)：３型言語
• 文法が生成する言語の複雑さにより，文法
（言語)を階層的に分類したもの．
• 上ほど緩く，下ほど制約が厳しい．
• 下の言語は上の言語にそれぞれ包含される．
5
2015/7/15
万能チューリング機械
万能チューリング機械(続き)
• テープを２つの部分に分ける．
• 計算機の数学的モデル
• 第一の部分には，書き換え規則により引き起
こされる動作の系列をコード化する．
• 第二の部分には，（通常どおり)認識する記号
列が書かれている．
• 第一の部分に書かれた動作の系列がプログ
ラム，第二の部分に書かれた記号列がデー
タに対応する．
• 第一の部分のコードを解読し，その指示に
沿って第二の部分の記号列を認識する．
チューリング機械における
計算量
• 認識するまでにヘッドが動いたテープ上のマ
スの総数を，認識に必要な時間計算量(time complexity)という．
• 決定性と非決定性では，認識する言語のクラ
スに差はない．しかし，認識にかかる計算量
では差がある．
計算量
• 例：
ソーティングアルゴリズム 3,6,2,9,4,2,1,...
2
バブルソート o(n )
クイックソート o(n*log n)
• オーダーの違い
n=10
n=100
n=1000
n=10000
n 2
100
10000
1000000
100000000
n * log n
33.2
664
99600
1328000
2
n
1012
PとNP
（多項式時間計算可能性）
• 決定性TMで文の長さMの多項式のオーダーの時間
計算量で認識できる言語のクラスの認識問題を「ク
ラスP」という．
• 非決定性TMで，さらに非決定的な分岐点で正しい
選択をして，Mの多項式のオーダーの時間計算量
で認識できる言語のクラスの認識問題を「クラスNP」
という．
• NPの問題は，Mの指数関数に比例する時間計算量
がかかると推測される．
10
301
10
3010
30100
10
NP完全問題
• NP問題の中のあるものは，多項式時間計算不
可能である（P≠NP予想)．
NP
NP完全
P
巡回セールスマン問題
整数線形計画法
ナップザック問題
6
2015/7/15
決定可能性(decidability)
決定可能性(続き)
• 手続きによって，言語に属する文を一つずつ
もれなく生成できるとき，その言語を「帰納的
可算(recursively enumerable)」という．
• 0型言語は帰納的可算な集合．
• TMによって決定可能な言語を帰納的という．
• すべての入力文が言語に属するかどうかを
決定する（判断し，停止する)手続きが存在す
るとき，その言語を認識する問題は「決定可
能」であるという．
決定可能性
（あるいは計算可能性）
• あるクラスAに対して，各インスタンスa∈Aが
性質Pを持つかどうか（P(a)が真か偽か）を決
定するアルゴリズムが存在するとき，Aに対す
るPの決定問題は「決定可能」という．
• TMはアルゴリズムの定義を与える．
• 言語に属する記号列が問題をコード化したも
のとみなしている．
帰納的可算
帰納的
期末試験
• 7月21日に「オートマトンと言語理論」の試験
を行います。
• 授業中に行った演習問題を復習しておいてく
ださい。
• 資料の持ち込みはできません。
• 説明問題も少し出ます。
• 試験結果は7月24日までにWebページで発表
します。落ちた人は7月28日に追試です。
7

Download Report