正則言語 2011/6/27
形式言語 Noam Chomsky() 近代言語学者・哲学者・政治思想家 言語を形式的に解析しようとする試み 形式文法から言語を構築していく 情報理論との関連性（オートマトン、構文解析、チューリングマシン等）
形式文法 ある定められた規則（文法）から導出される文字列 G=(N,∑,P,S) N 非終端記号の有限集合 ∑ 非終端記号の有限集合 ∑ 非終端記号の有限集合 P 生成規則（有限） S 開始記号
形式文法の例（文脈自由文法） 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
Chomsky階層 1956 形式文法のクラス 正則文法 Regular Grammar 文脈自由文法 Context Free Grammar 文脈依存言語 Context-Sensitive Grammar 句構造文法 Phrase Structure Grammar RG ⊂ CFG ⊂ CSG ⊂ PSG
正則言語 生成規則が次の形のもの A → aB C→b 例外として S→ε（空文字列） 特長 有限性オートマトンと等価
正則言語の例 生成規則が次の形のもの N={A,B,S} ∑＝｛0,1} P={ A → 1B,B→0,S→１A} 等価なオートマトン S → A → B → F 1 1 0 この言語は110を生成する
文脈自由文法 構成規則が以下のような形のもの A→a (A∈N,a∈(N∪∑)＊） 例 N={A,B,S} ∑＝｛0,1,2｝のとき P={S→A、A→1、B→02,A→0B1｝ プッシュダウンオートマトンとの関連
文脈依存文法 生成規則が以下のような形のもの βAγ → βaγ P={a、β、γ∈(N∪∑)＊ ,A ∈N,a≠ε} 線形高速オートマトン
句構造文法 構成規則が以下のような形のもの α→β P={α∈(N∪∑)＊ N(N∪∑)＊ ）,β ∈(N∪∑)＊} 左辺に少なくとも一つの非終端記号があるだけ チューリングマシンとの関連
正則文法と有限オートマトン 正則便法と等価な有限オートマトンを構成できる N={A,B} ∑＝｛0,1} P={ A → 1B,B→0,S→１A} S → A → B → F 1 1 0
正則文法における反復補題 直観的な理解 正則文法G１は有限オートマトンに変換できる 有限オートマトンには有限の状態しかない 長い文字列は必ず同じ状態に到達する ループを何回回るような文もG1は受理する
正則文法における反復補題 Lが正則言語なら、ある定数nが存在し、Lに属する長さがnまたはそれ以上のすべての語Wに対し次のような語X,Y,Zが存在する W=XYZ |XY|≦n |Y|≧1 K=1,2,3,… に対し XY*Z
正則文法における反復補題 S 0 A X 1 B 0 C Y 1 B 1 D Nの個数＜|Z| Z 0 {S,A,B,C,D} 010110 必然的に重複する状態が出る
証明 ある生成文字列長|N|に対し、同じ状態（生成規則）Fが複数（ F１、F2 ）存在する １～F１で生成される文字列をX、 F1＋１～F2をY、 F2~NをZとする 定義より| Y|≧1 |XY|≦n F1＋１～F2はループを構成し何回も文字列を生成できる XY*Z
正則言語における反復補題の意味 正則言語は反復定理の特長をもっている ある言語をもってきて、それが反復定理をみたさなければ、正則言語ではない 文脈自由言語についても反復定理が適用できる ある条件を満たさなければ文脈自由言語ではない
参考文献 Wikipedia オートマトン・言語理論 富田悦次 横森 貴 森北出版株式会社基礎情報工学シリーズ５