講義予定 プレイスメントテスト 講義の事務連絡 本日の予定

2015/7/3
講義予定
• 6月23日
離散システム論
オートマトンと形式言語論(1)
• 6月 30日
• 7月 7日
知能システム科学
新田克己
• 7月 14日
• 7月 21日
•
プレイスメントテスト
• オートマトンと言語理論の基礎知識についての
テスト
• 6月28日までに合格者を発表
• 合格者：講義に出席する必要なし。期末試験
を受験する必要なし。課題レポートを
提出することによって単位取得。
• 不合格者：講義に出席し、期末試験に合格
することによって単位取得。
毎回、講義の途中で演習を行う。
プレイスメントテスト
形式言語とオートマトン
決定性有限オートマトン
非決定性有限オートマトン
正規文法
プッシュダウンオートマトン
文脈自由文法
チューリングマシン
文脈依存文法
決定可能性、計算量
期末試験（「形式言語とオートマトン」のみ）
7月 28日 追試（樺島先生、宮下先生、新田）
講義の事務連絡
• http://www.ntt.dis.titech.ac.jp/sm/risan
/index.html
• 講義資料と事務連絡については上記ページ
にアクセスすること。
本日の予定
• ～15時55分 テスト
• 16時～16時35分
オートマトンと形式言語論の入門
離散システム論
オートマトンと形式言語論(1)
• 本日のPPT資料は、明日までに本講義のWebページ
にアップしますので、各自、ダウンロードしてください。
• 来週以降のPPT資料は、その週の月曜の夕方までに
アップします。各自、講義の始まる前にプリントして
持参してください。
知能システム科学
新田克己
1
2015/7/3
オートマトン理論とは
• オートマトン理論
＝抽象的な計算装置（機械）の研究
• 1930年代
A.Turing
チューリングマシンの提唱。
計算機械ができることとできないことの
境界を明確に記述する目的
オートマトン理論とは
• 1940年代、1950年代
より簡単なモデル（有限オートマトン）の研究。
脳の機能のモデルとして提案。
• 1950年代
N. Chomsky 形式文法
用語の定義（その１）
• 1969年
S. Cook 計算量
・コンピュータで効率よく解ける問題のクラス
・原理的には解けるが、実際には非常に多くの
時間がかかるため、小規模の場合しか解けな
い問題のクラス
用語の定義（その２）
• アルファベットをｎ個並べたものの集合をΣｎと
すると，
0
Σ ＝ ｛ε｝
Σ＊＝ Σ0＋Σ1＋‥‥＝ ∑
Σ+＝ Σ1＋ Σ2 ＋ ‥ ‥ ＝ ∑
Σ
• 文字(character)： 言語を構成する基本単位
• アルファベットΣ： 文字（記号）を要素とする
空でない有限集合
• アルファベット上の記号列： Σの記号を任意
個取り出し連接して並べたもの
• 記号列の長さ：記号列中の記号の個数
• 空列ε（あるいはλ）：長さ0の記号列
たとえば
• Σ＝｛a,b,c}なら
Σ0＝｛ε｝，
Σ1＝｛a,b,c},
Σ2＝｛aa,ab,ac,ba,bb,bc,ca,cb,cc}
…
Σ
Σ＊： Σの閉包(closure)，アルファベット上の
記号列全体の集合
Σ＝{A～Z, a～z, [,] , [. ], スペースなど}
ならΣ＊はすべての英語の単語，文，テキストを
含む集合
2
2015/7/3
言語の形式的定義
• Σ＊中の記号列には，でたらめな記号列もあるが，
ある言語の文となる場合もある．
• たとえば、「は太郎いるねよ｣，「太郎はいるよね」
• 言語L: Σ＊の部分集合，言語の文の集合
• 文法： 記号列が言語に属するかどうかを決定する
ための知識，文に関する生成規則の集合
文法の定義（その１）
文法G=＜VN，VT，P，σ＞
VN: 非終端記号の集合 ex: {σ,X,Y}
VT: 終端記号の集合 ex: {a,b,c}
P: 生成規則（書き換え規則）の集合
ex: {X→Y, X→a}
σ： 初期記号 σ ∈ VN
文法の定義（その２）
• 書き換え規則：α→β
α∈V+，β∈V*，V=VN∪VT
• 非終端記号VN： 自然言語の文法では，品詞
などの文法用語
ex: S（初期）, NP（名詞句）, VP（動詞句）, N（名詞）,….
• 終端記号VT: 自然言語では，単語
ex: I, girl, a, saw, ….
たとえば
S→NP，VP．
NP→Det，N．
NP→N.
VP→V，NP.
Det→a.
N→I. N→girl.
V→saw.
…
ここで，Sが初期記号
S
NP, VP
N,VP
I,VP
I,V,NP
I,saw,NP
I,saw,Det,N
I,saw,a,N
I,saw,a,girl
S
NP,VP
N,VP
I,VP
I,V,NP
I,saw,NP
I,saw,N
I,saw,I
書き換え規則の読み方
導出(derivation)
• S→NP，VP.
1．文（S）は名詞句（NP）と動詞句（VP）から構成
される
2．Sがあるなら，NPとVPに書き換えることができ
る
• 書き換え規則α→βがある場合，記号列AαB(A, B∈V*）はこの規則によりAβBに書き換えられ
る．これを導出といい，
AαB⇒AβB
で表す．
ex: abbaαbba⇒abbaβbba
＊
• ⇒ は導出の任意回の繰り返しを意味する．
3
2015/7/3
文法を用いた言語の定義
• 終端記号からなる記号列wが初期記号σから
導出されるとき，wを文(sentence)と言う．
• 言語L(G)：文法Gによって生成される言語
＊
L(G)=｛ｗ｜ｗ∈VT*， σ⇒ ｗ｝
文法Gにより初期記号σから生成される文の
集合
たとえば
• 初期記号Sから書き換え規則を適用していくと，
S⇒ NP VP ⇒ N VP ⇒ I VP⇒ I V NP ⇒
I saw NP ⇒ I saw Det N⇒ I saw a N⇒
I saw a girl
このように最も左の非終端記号を書き換えていく導出
を最左導出(leftmost derivation)と言う.
*
S⇒ I saw a girl
たとえば
• アルファベット｛0，１｝上の回文集合
L={ε，0，1，00，11，010，1101011，…｝
オートマトン
• 言語を計算機上で認識（受理）するための
抽象的機械（モデル）
S→ε S ⇒ 0S0 ⇒ 01S10 ⇒
S→0 011S110 ⇒ 0111110
S→1
S→0S0
S→1S1
オートマトンの一般的構成
• 制御部：テープの読み書きヘッド＋状態
• 読み込んだ記号により状態を変化させる．
• 初期状態から開始し,入力記号列をすべて
読み込んだ後の状態が最終状態なら，入力記号列
を認識（受理）したと言う.
• 入力記号列を受理しないことを棄却するとも言う．
• 逆に,初期状態から最終状態までの過程で記号列を
生成することもできる．
(決定性)有限オートマトン
((deterministic) finite automaton)
• M=＜K, Σ, q0, F, δ＞
– K: 状態の有限集合
– Σ：アルファベット
– q0： 初期状態, q0∈K
– F: 最終状態の集合, F⊂K
– δ： 状態遷移関数, δ：K×Σ→K
4
2015/7/3
状態遷移図
• 有限オートマトンと対応する有向グラフ表現
• ノードは状態
• 最終状態は,◎で表現する
受理言語（その１）
• δ＾：K×Σ*→K
１) δ＾(q,ε)=q
２) 任意の記号列w, 記号aに対して,
δ＾(q,wa) = δ(δ^(q,w),a)
状態遷移
• 読み込んだ記号と内部状態の組み合わせで,
次の状態を決定する
• 状態qiで入力aが与えられたとき,状態qjに遷
移することをδ(qi,a)=qjと表現する
受理言語(その２）
• Mの受理言語L(M):Mが受理する記号列すべ
ての集合
• L(M)={w∈Σ*｜δ＾（q0,w)∈F}
• 有限オートマトンの受理言語は,正規言語
(regular language)と呼ばれる.
• 有限オートマトンMと記号列wに対して,
δ^(q0, w) ∈Fなら, wはMに「受理される
(accepted)」と言う.
たとえば
• 文字aが任意個並んだ文字列を受理するオー
トマトン
• L(M)=｛ε, a, aa, aaa, …}
たとえば
• 名詞句 N+ PREP N+ を受理するオートマトン
（N:名詞, Prep:前置詞）
5
2015/7/3
状態遷移図と
受理される文字列集合の関係
(続き)
• リンクが2つ直列： 文字を2つ連接した文字列
が対応(ab)
• ループがある場合,ループをたどる文字列をx
とすると,その閉包x*が対応
• ノード間に2つのリンクが並列： 2つの文字の
集合（OR）が対応(a+b)
たとえば
• これら3つによって表現された文字列の集合
を正規言語と言う.
演習問題
1．a(b+c)*aに対応する有限オートマトンの状態
遷移図を書いてみましょう.
2．図の有限オートマトンの受理する言語を説
明してください．
(a+b)c(b(a+b)c)＊a
6