形式言語とオートマトン2008 ー第4日目？ー

形式言語とオートマトン2008
ー第11日目ー
東京工科大学
コンピュータサイエンス学部
亀田弘之
だんだん終わりが見えてきました．
そろそろ全体をまとめていきましょう．
今回も復習から
• 今日はざっと見ていきましょう．
確認(1)
• 有限オートマトン(FA)
– FAの定義と記述法
テープ上を一方向に動くヘッド
（テープ上の記号を順次読みながら内部状態を遷移）
M = <K, Σ, δ, q0, F> （５つ組）
状態遷移図
様相（configuration）
– FAの種類
決定性FA（DFA）
非決定性FA（ε遷移のあるものとないもの）
– 言語認識能力はどのFAでも同じ。
正規言語（正規表現）を認識
確認（２）
•
正規表現を認識するFAの存在とその構成法
1.
2.
3.
4.
5.
正規表現αが与えられる。
正規表現αに対して、ε-NFA を構成する。
ε-NFA をDFAに書き換える。
DFAを状態数最少のDFA(Min-DFA)に書き換える。
Min-DFAをシミュレートするプログラムを作成する。
(上記５はまだ説明していません！)
確認（３）
• プッシュダウンオートマトン(PDA)
– スタックの定義
データ構造：
・配列（またはアレイ）
・リスト
・スタック
・キューなど
スタックの構造と動作（pop-up と push-down）
LIFO (Last-In First-Out) 型のメモリ
– PDAの定義と記述法
テープ上を一方向に動くヘッド＋スタックメモリ
（テープの記号を順次読み、スタック上の記号を準じ読
み書きしながら内部状態を遷移）
M = < K, Σ, Γ,δ, q0, Z0, F > （７つ組）
状態遷移図
様相（configuration）
確認（４）
スタックとPDAのイメージ図
Push down
Pop up
LIFO (Last In First Out)
最後に入れたものが最初に取り出される。
確認（５）
• プッシュダウンオートマトン(PDA)
– PDAの種類
決定性プッシュダウンオートマトン
Deterministic pushdown automaton (DPDA)
非決定性プッシュダウンオートマトン
Nondeterministic pushdown automaton (NPDA)
– 言語認識能力はNPDAの方が高い。
FAは正規言語（正規表現）を認識
NPDAは文脈自由言語を認識
DPDAよりもNPDAの方が言語認識能力大
確認（６）
• チューリングマシン(Turing Machine; TM)
– TMの定義と記述法
 テープ上を左右どちらにも動けるヘッド
（テープ上の記号を順次読み、テープ上に時として記号を書き込み
ながら、そのたびごとに内部状態を遷移）
 M = < K, Γ, Σ, δ, q0, B, F > （７つ組）
 状態遷移図
 様相（configuration）
– TMの種類
 決定性TM（DTM）
 非決定性TM(NTM)
– 言語認識能力はどのTMでも同じ。
 句構造言語（句構造文法に適った文）を認識
確認（７）
• オートマトンと形式言語（形式文法）とは相互
に密接な関係がある．
• したがって，形式言語も深く学ぶ価値がある．
• オートマトンの応用分野：
– 計算モデル
• 計算概念の定式化
• 計算可能性
• 計算量
– その他
• 形式言語の応用分野：
– 自然言語処理・音声処理
• カナ漢字変換システム
• 機械翻訳システム
• 自動通訳システム
– プログラミング言語とその処理
• コンパイラ設計
• プログラミング言語設計
– その他
確認（８）：言語の形式的定義
• 単語ｗ： X1, X2, X3, ・・・, Xn （はじめに単語ありき）
• 語彙V (Vocabulary) ：単語の集合
V = { X1, X2, X3, ・・・, Xn } (有限集合)
• 文(sentence)：単語の並び（単語の列）
（注）
– Vの要素( X1 や X2 など)は単語
– Xa Xb Xc Xd など，単語の並びは何でも文と考える．
– でも何でも良いわけではない。
確認（９）：考察
• 文は無限個存在する。
（単語は有限個）
• 言語L（例えば英語）として意味のあるものと
そうでないものとが混ざっている。
⇒ 言語Lとして意味のある文をすべて集めた集合
は、１つの言語（今の場合はL）を定める。
⇒ 言語Lとして意味があるものとないものとを
区別したい。
つまり、任意の文（単語列）に対して、それが
言語Lの文かそうではないのかを判定したい。
• そんなことできるのだろうか？
でも、人間はやっているよ！
じゃあ、できるんだね！（信念）
自動機械（オートマトン）を作ってみよう！
作成のためのアイデア
• はじめに言語Lの文すべてを知っているなら
ば、下記のような機械ができる。
文S1
オートマトン
S1 S2 S3
… Sn
S1は言語Lの
文だよ！
問題点１
• でも、
「言語Lの文すべてを知っている」
なんて、不可能だよ！
• 例：「２００8年6月23日、形式言語とオートマト
ンの授業が、講実4０3教室で、パワーポイン
トを用いて行われた。」という文をあなたは
事前に知っていましたか？
問題点２
• もし何らかの方法により、事前に言語Lのすべての文
を知っていたとしても．．．
s = get_sentence();
if ( s ∈ Lの文の集合 ) then
s は Lの文である
else
s は Lの文ではない
end if
Lの文の集合が無限集合のときは、このプログラムは
停止しないことがある！！！
それではどうしようか？！
ここまでのまとめ
• 言語
– 意味のある文（言語Lの文）の集合
• 文法の必要性
– ある言語（例えば日本語）の文すべてを
あらかじめ知っているなんてことは不可能！
• オートマトン
– ある文が対象としている言語Lの文なのかを自動
判定する装置
どうも文法が大切らしい。
もう少し文法について学んでみよう！
ホントにしゃべれるよ
うになるのかなぁ
普遍文法という発想
• すべてのヒトは、
– 言語に依存しない普遍的な処理能力をもった装
置(device)を生得的に持っており、
– 個別言語に関する知識は後天的に獲得されるか
らだ。
僕にもこん
な装置がほ
しいなぁ…
これが私の基
本的考えです。
写真の出典：Wikipediaより
• その知識は、「文法」という形で獲得される。
• Chomskyはそのように考えた。
• それでは彼の考えを見てみよう。
文法の定義
• 文法G=（ Vn, Vt, P, S ）：
– ただし、
•
•
•
•
Vn:
Vt:
P:
S:
非終端記号の集合
終端記号の集合
書き換え規則の集合
開始記号
重要
文法
• 文法G=（ Vn, Vt, P, S ）：
– ただし、
• Vn: 非終端記号の集合
<= 構文木構成要素の集合
• Vt: 終端記号の集合
<= 単語の集合
• P: 書き換え規則の集合
• S: 開始記号
例１-1
• G=(Vn, Vt, P, S)
– Vn = { S, NPs, NPo, VP, PN, DET, N }
– Vt = { I, You, have, throw, a, the, book, ball }
– P = { ①：S → NPs VP,
②：NPs →
PN,
③：PN → I,
④：PN → You,
⑤：NPo → DET N,
⑥：VP → V NPo,
⑦：DET → a,
⑧：DET → the,
⑨：N → book,
⑩：N → ball,
⑪：V → have,
⑫：V → throw }
例１-2
• S =>
=>
=>
=>
=>
=>
=>
=>
NPs VP
PN VP
I
VP
I V NPo
I throw NPo
I throw DET N
I throw a N
I throw a ball
①
②
③
⑥
⑫
by ⑤
by ⑦
by ⑩
by
by
by
by
by
開始記号
• S =>
=>
=>
=>
=>
=>
=>
=>
例１-2
非終端記号
NPs VP
PN VP
I
VP
I V NPo
I throw NPo
I throw DET N
I throw a N
I throw a ball
終端記号
適応規則
①
②
③
⑥
⑫
by ⑤
by ⑦
by ⑩
by
by
by
by
by
例１-2
• S =>
=>
=>
=>
=>
=>
=>
=>
文
NPs VP
PN VP
I
VP
I V NPo
I throw NPo
I throw DET N
I throw a N
I throw a ball
①
②
③
⑥
⑫
by ⑤
by ⑦
by ⑩
by
by
by
by
by
終端記号のみの列
例１-2に対する問題
• これは木(tree)として記述せよ。
• この文法Gにより生成される文をすべて列挙
せよ。
言語の定義
• 言語Lとは、文法Gにより生成されるあらゆる
文の集合のこと。
• つまり、L＝L(G)。
問題（Palindrome）
• Palindromeのみを生成する文法を示せ。
ただし、
G=( Vn, Vt, P, S )
Vn = { S }, Vt = { a, b, c }
とする。
ここまでのまとめ
•
•
•
•
人間の頭の中には、言語処理装置がある。
すべての文を記憶しているわけではない。
文法として記憶している。
文法とは何か？
– 規範文法(Prescriptive Grammar)
– 記述文法(Descriptive Grammar)
• 形式文法と形式言語
形式文法と形式言語
• 文法G = （ Vn, Vt, P, S ）：
– ただし、
• Vn（非終端記号の集合）: 0 < #Vn < +∞
• Vt: 終端記号の集合:
0 < #Vt < +∞
• P: 書き換え規則の集合
{α→β| α, β ∈ (Vn∪Vt)*}
• S:
開始記号(S∈Vn)
• 言語L = L(G) = { x | S =*> x }
– ただし、S => ・・・ => x ∈ Vt
形式文法と形式言語（例）
• 文法G = （ Vn, Vt, P, S ）：
– Vn ={S}, Vt={}
– P={ }
• 言語L = L(G) = { x | S =*> x }
言語の階層（重要）
• 言語は文法の種類に応じて、階層構造をなし
ている。
– 句構造言語
– 文脈依存言語
– 文脈自由言語
– 正規言語
⇔
⇔
⇔
⇔
句構造文法
文脈依存文法
文脈自由文法
正規文法
Chomsky階層
(Chomsky Hierarchy)
とも言う。
一般的
特殊的
句構造文法
(Phrase-Structure Grammar; PSG)
• 文法G = （ Vn, Vt, P, S ）：
– Vn（非終端記号の集合）:
0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{α→β| α, β ∈ (Vn∪Vt)*}
– S:
開始記号(S∈Vn)
句構造文法
(Phrase-Structure Grammar; PSG)
• 文法G = （ Vn, Vt, P, S ）：
– Vn（非終端記号の集合）:
0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{α→β| α, β ∈ (Vn∪Vt)*}
– S:
開始記号(S∈Vn)
句構造文法
(Phrase-Structure Grammar; PSG)
• 文法G = （ Vn, Vt, P, S ）：
– Vn（非終端記号の集合）:
0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{α→β| α, β ∈ (Vn∪Vt)*}
– S:
開始記号(S∈Vn)
ここに制限が付くと他の
文法になる。
文脈依存文法
(Context-Sensitive Grammar; CSG)
• 文法G = （ Vn, Vt, P, S ）：
– Vn（非終端記号の集合）: 0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{αXβ→αγβ| α, β ∈ (Vn∪Vt)*, X∈Vn,
γ∈ (Vn∪Vt)+ }
– S:
開始記号(S∈Vn)
文脈自由文法
(Context-Free Grammar; CFG)
• 文法G = （ Vn, Vt, P, S ）：
– Vn（非終端記号の集合）:
0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{ X→α| α∈ (Vn∪Vt)*}
– S:
開始記号(S∈Vn)
正規文法
(Regular Grammar; RG)
• 文法G = （ Vn, Vt, P, S ）：
– Vn（非終端記号の集合）:
0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{X→aY, X→b| X,Y∈Vn, a,b ∈ Vt*}
– S:
開始記号(S∈Vn)
生成規則部分の比較
•
•
•
•
PSG:
CSG:
CFG:
RG:
α→β
αXβ→αγβ
X→α
X→aY, X→b
– ただし、
• α，β∈V*
• X, Y∈Vn
・γ∈V+
・a, b∈Vt
・V=Vn∪Vt
重要
Chomsky階層
PSG
CSG
CFG
RG
文法（言語）とオートマトン
----------------------------------------------------文法
処理装置
----------------------------------------------------• 句構造文法(PSG)
⇔ ？
• 文脈依存文法(CSG)
⇔ ？
• 文脈自由文法(CFG)
⇔ ？
• 正規文法(RG)
⇔ ？
-----------------------------------------------------
文法（言語）とオートマトン
---------------------------------------------------------------文法
処理装置
---------------------------------------------------------------• 句構造文法(PSG)
⇔
Turing 機械
• 文脈依存文法(CSG) ⇔
線形有界オートマトン
• 文脈自由文法(CFG) ⇔
プッシュダウンオートマトン
• 正規文法(RG)
⇔
有限オートマトン
---------------------------------------------------------------これも覚えておいてください．
言語の包含関係
L（PSG) ⊃ L(CSG) ⊃ L(CFG) ⊃ L(RG)
このうち、大切なのはCFGとRG。
なぜ大切か
というと…
CFGとRG
• CFG（文脈自由文法）：
– プログラミング言語設計
– コンパイラの構文解析
– 自然言語処理（機械翻訳・仮名漢字変換）
• RG（正規文法）：
– 正規表現（検索・コンパイラの語彙解析）
CFGの特徴
1.
2.
3.
4.
5.
CFGには標準形がある。
導出の過程を木で表現できる（導出木の存在）。
解析手法が豊富に知られている。
自然言語処理に部分的に適用できる。
プログラミング言語設計に利用されている。
ここから新しい内容
１．CFGの標準形
• Chomskyの標準形
• Greibachの標準形
教科書p.174
Chomskyの標準形
• どの書き換え規則も，
– 右辺がただ一つの終端記号になっているか，
– ２個の非終端記号だけである
という条件を満たしている．
つまり，…
• A → BC
•A → a
• ただし，A,B,Cは非終端記号，aは終端記号
Greibachの標準形
• どの書き換え規則も，その右辺が
– 左端にただ一つの終端記号を有し，かつ，
– その終端記号に続いて０個以上の非終端記号か
らなっている，
という条件を満たしている．
つまり，…
•A → a
• A → aB
•A → aBC
•A → aBCD
•…
•A → aBCD…E…F
ただし，A～Fは非終端記号，aは終端記号
Chomskyの標準形
• 任意のCFGにおける書き換え規則群Pは、
A→BC または A→a という形だけで表現
できる。
Greibachの標準形
• 任意のCFGにおける書き換え規則群Pは、
A→aα という形だけで表現できる。ただし、
X∈Vn, a∈Vt, α∈Vn*。
Chomskyの標準形への変換方法
（教科書 p.177 問題6.9）
例示
• G=< { S, A, B }, { a, b }, P, S >
S → bA
A→ a
S → aB
B → b
A → aS
A → bAA
B → bS
B → aBB
これと等価なChomsky標準形
文法を求めよう．
結果
S→C1A
D1→AA
B→C6D2
C2→a
C4→a
B→b
A→C2S
S→C4B
D2→BB
C3→b
C5→b
A→C3D1
B→C5S
C1→b
A→a
C6→a
練習問題
G=< { S, T, L }, { a, b, +, -, ×, /, [, ] }, P, S >
P:
S→T+S
S →T-S
S →T
T →L×T
T →L/T
T→L
L →[S]
L →a
L →b
1. 言語L(G)はどのようなものか？簡単に説明せよ．
2. L(G)を生成するChomsky標準形文法を求めよ．
3. L(G)を生成するGreibach標準形文法を求めよ．
試験に出るかも？
ここまでのまとめ
• 言語には階層がある（Chomsky階層）
• 正規言語（正規文法）は語句解析に深い関係
がある。
• 文脈自由言語（文脈自由文法）は構文解析に
深い関係がある。
• 文脈自由文法には標準形が存在する．
その他の重要事項
定理１
• 与えられたｃｆｇ Gによって生成される言語
L(G)が，空集合かそうでないかを決定するア
ルゴリズムが存在する．
定理２
• 与えられたｃｆｇ Gによって生成される言語
L(G)が，有限集合か無限集合かを決定する
アルゴリズムが存在する．
（つまり，生成される文が有限個なのか無限
個なのかを決定するアルゴリズムが存在する，
ということ．）
定理３
• 文法Gが自己埋め込みでないcfgであれば，
L(G)は正規集合である．
定義（自己埋め込み）：
どちらも空でない文字列α1，α2について
A ＝＞ α1 A α2 となるような非終端記号Aが
存在すること．
注
• G=< { S }, { a, b }, P, S >
P:
S→aSa
S →aS
S →a
S →b
S →bS
文法と言語とオートマトン
•
•
•
•
句構造文法(PSG)
文脈依存文法(CSG)
文脈自由文法(CFG)
正規文法(RG)
言語の階層（重要）
• 言語は文法の種類に応じて、階層構造をなし
ている。
– 句構造言語
– 文脈依存言語
– 文脈自由言語
– 正規言語
⇔
⇔
⇔
⇔
句構造文法
文脈依存文法
文脈自由文法
正規文法
Chomsky階層
(Chomsky Hierarchy)
とも言う。
一般的
特殊的

Download Report