正則言語 2011/6/27.

Presentation on theme: "正則言語 2011/6/27."— Presentation transcript:

1 正則言語 2011/6/27

2 形式言語 Noam Chomsky() 近代言語学者・哲学者・政治思想家 言語を形式的に解析しようとする試み 形式文法から言語を構築していく
情報理論との関連性（オートマトン、構文解析、チューリングマシン等）

3 形式文法 ある定められた規則（文法）から導出される文字列 G=(N,∑,P,S) N 非終端記号の有限集合 ∑ 非終端記号の有限集合
∑　非終端記号の有限集合　　 P 生成規則（有限）　　　　　　 S 開始記号　　　　　　　　　　　

4 形式文法の例（文脈自由文法） N=｛A,B｝ ∑=｛0,1} P={S→0A, A→1A, A→AB,B→0,A→1｝
　　　　　G１＝（N,∑,P,S) N=｛A,B｝ ∑=｛0,1} P={S→0A, A→1A, A→AB,B→0,A→1｝ S→0A→01A→01AB→0110 S→0A→01

5 Chomsky階層 1956 形式文法のクラス 正則文法 Regular Grammar
文脈自由文法　Context Free Grammar 文脈依存言語　Context-Sensitive Grammar 句構造文法　Phrase Structure Grammar RG ⊂ CFG ⊂ CSG ⊂ PSG

6 正則言語 生成規則が次の形のもの A → aB C→b 例外として S→ε（空文字列） 特長 有限性オートマトンと等価

7 正則言語の例 生成規則が次の形のもの N={A,B,S} ∑＝｛0,1} P={ A → 1B,B→0,S→１A} 等価なオートマトン
S →　A → B →　F 　 この言語は110を生成する

8 文脈自由文法 構成規則が以下のような形のもの A→a (A∈N,a∈(N∪∑)＊） 例 N={A,B,S} ∑＝｛0,1,2｝のとき
P={S→A、A→1、B→02,A→0B1｝ プッシュダウンオートマトンとの関連

9 文脈依存文法 生成規則が以下のような形のもの βAγ → βaγ P={a、β、γ∈(N∪∑)＊ ,A ∈N,a≠ε}
線形高速オートマトン

10 句構造文法 構成規則が以下のような形のもの α→β P={α∈(N∪∑)＊ N(N∪∑)＊ ）,β ∈(N∪∑)＊}
左辺に少なくとも一つの非終端記号があるだけ チューリングマシンとの関連

11 正則文法と有限オートマトン 正則便法と等価な有限オートマトンを構成できる N={A,B} ∑＝｛0,1}
P={ A → 1B,B→0,S→１A} S　→　A →　B → F 　　　0　

12 正則文法における反復補題 直観的な理解 正則文法G１は有限オートマトンに変換できる 有限オートマトンには有限の状態しかない
長い文字列は必ず同じ状態に到達する ループを何回回るような文もG1は受理する

13 正則文法における反復補題 Lが正則言語なら、ある定数nが存在し、Lに属する長さがnまたはそれ以上のすべての語Wに対し次のような語X,Y,Zが存在する W=XYZ |XY|≦n |Y|≧1 K=1,2,3,…　に対し　XY*Z

14 正則文法における反復補題 S 0 A X 1 B 0 C Y 1 B 1 D Nの個数＜|Z| Z 0 {S,A,B,C,D} 必然的に重複する状態が出る

15 証明 ある生成文字列長|N|に対し、同じ状態（生成規則）Fが複数（ F１、F2 ）存在する １～F１で生成される文字列をX、
　　F1＋１～F2をY、 　　F2~NをZとする 定義より| Y|≧1 |XY|≦n F1＋１～F2はループを構成し何回も文字列を生成できる XY*Z

16 正則言語における反復補題の意味 正則言語は反復定理の特長をもっている ある言語をもってきて、それが反復定理をみたさなければ、正則言語ではない
文脈自由言語についても反復定理が適用できる ある条件を満たさなければ文脈自由言語ではない

17 参考文献 Wikipedia オートマトン・言語理論 　富田悦次　横森　貴 　森北出版株式会社基礎情報工学シリーズ５