3. プッシュダウンオートマトンと文脈自由文法 1
3-1. プッシュダウンオートマトン オートマトンはメモリがほとんど無かった この制限を除いた機械を考える 理想的なスタックを利用できるようなオートマトンをプッシュダウンオートマトン (Push Down Automaton,PDA) という 0 1 入力テープ 1 a 1 1 0 1 スタッb 入力テープを一度走査したあと ク2 入力テプを度走査したあと はい ならランプ点灯 いいえ ならランプ消灯
ック有限制御部タPDA の概略 有限制御部 読み取りヘッド 0 1 入力テープ b PDA を定める要素スa 入力テープテープに書ける文字 有限制御部内部状態初期状態状態変化受理かどうかの判断 スタック ( 無限長 ) スタックに書ける文字 3
PDA の数学的定義 PDAは P = ( Q, Σ, Γ, δ, q0, F) の6 項組で与えられる ここで 1. Q は有限集合で 状態を表す 2. Σ は有限集合で 入力アルファベットを表す 3. Γ は有限集合で スタックアルファベットを表す 3. δ は Q Σ ε Γ ε から P ( Q Γ ε ) への写像 ( δ : Q Σ ε Γε P ( Q Γε ) ) で 状態遷移を表す δ を状態遷移関数という 4. q 0 Q は 初期状態を表す 5. F Q は受理状態の集合を表す ここで Σ = {} = ε Σ ε Γ {} である ε Γ ε 4
PDA の図式表現 ( 状態遷移図 ) PDA は 状態遷移図で表現できる ( q', t') δ ( q, s, t) のとき 入力記号 st, t' q q ' 状態の変化 スタックの変化 スタック先頭の記号をからへ変化させる t t ' push('): t ε t ' t = pop () : t ε 5
PDA の例 B n n = {0 1 n 0} を認識するPDA PDA 例 1 P P ε, ε $ 1 q 1 q 2 0, ε 0 10 1,0 ε q 4 ε,$ ε q 3 1, 0 ε 6
形式的定義 P = ( Q, Σ,Γ, δ, q, F) 1 1 ただし Q= { q1, q2, q3, q4} Σ={0,1} {0,$} ( 状態集合 ) Σ= ( 入力アルファベット ) Γ= ( スタックアルファベット ) F スタックの 底 を表す特別な記号 q 1 ( 初期状態 ) = { q, q } ( 受理状態 ) 1 4 7
δ 状態遷移関数 入力 0 1 ε スタック 0 $ ε 0 $ ε 0 $ ε q 1 2 q {( q,0)} {( q, ε )} 2 2 3 q {( q, ε)} {( q, ε)} 3 3 4 q 4 {( q,$)} この表において 空白は空集合 φ を表している 8
スPDA の状態遷移 w = 0011 による状態遷移 0, ε 0 0, ε 0 q ε, ε $ 1 q q q 2 タ2 $ 0 ック$ 1, 0 ε q 2 0 0 $ q 3 0 $ 1, 0 ε q 3 $ ε,$ ε q 4 9
例 2 次の言語を認識する PDA を与える R * { ww w {0,1} } ここで w R は w を逆に書いた文字列 P ε, ε $ 2 q 1 q 2 0, ε 0 1, ε 1 ε, ε ε q 4 0,0 ε q 3 ε,$ ε 1,1 ε 10
練習 P に対する形式的な定義を求めよ また 2 s = 10111101 に対するの遷移をスタックの内容と共に示せ P 2 11
3-2. 文脈自由文法 以前 DFAが認識できる言語のクラス ( 正規言語 ) に対して 異なる表現法 ( 正規表現 ) を与えた ここでは PDA が認識できる言語のクラス ( 文脈自由言語 ) に対して もう一つの表現法 ( 文脈自由文法 ) を与える 12
文脈自由文法とは 文法例 G 1 A A B 0 A 1 B ε 導出 A 0 A 1 00 A 11 00 B 11 00 ε 11 0011 文脈自由文法は生成規則あるいは書き換え規則と呼ばれる式の集合で定められる 生成規則の左辺は 一つの変数 ( 非終端記号 ) であり 右辺は変数とアルファベット ( 終端記号 ) の列である 文脈自由文法では 開始記号から生成規則を基に書き換えられる すべて記号が終端記号になった時点で終了する ( 上の例 G 1 では 開始記号は A としている ) 文脈自由文法において 終端記号列に変換する過程 ( 生成記号系列 ) を導出という 13
CFG のの形式的定義 CFGは C = ( V, Σ, R, S) の4 項組で与えられる ここで 1. V は変数 ( 非終端記号 ) と呼ばれる有限集合 2. Σ はアルファベット ( 終端記号 ) と呼ばれ有限集合 Vとは共通部分を持たない つまり V Σ= φ 3. Rは 生成規則の有限集合である ただし 生成規則の左辺は一つの非終端記号であり 右辺は変数と終端記号の文字列からなる * すなわち 各生成規則は A V, α ( V + ) として A α と表される 4. S V は開始記号 14
導出可能性を表す表現 ( ) * ある系列 α V + に任意回 ( k ( 1) 回 ) の規則の適用で * 系列が得れることを * β ( V + ) α β とも書く すなわち * は α β α = α α α = β のことである 1 2 k 15
文脈自由言語 (CFL) 文脈自由文法 (Context-Free Grammar,CFG) で 記述できる言語を 文脈自由言語 (Context-Free Language,CFL) と呼ぶ ある文脈自由文法 G に対して G から導出できる言語 を LG ( ) と書く 16
導出列 G が 000111 1 を導出できることを示す A 0A1 00A11 000A111 000B111 000ε111 000111 このような 生成規則の適用される順序を示したものを導出列とよぶ 17
構文解析木 文字列に対して 導出における生成規則の適用を図式的に表現できる このような導出過程を表す木状の図形を構文解析木と呼ぶ A A A A B 0 0 0 ε 111 18
CFG の例 2 G 2 < Sentence > < Noun Phrase >< Verb Phrase > < Noun Phrase > < Cmplxp Noun >< Cmplxp Noun >< P repp Phrase > < Verb Phrase > < Cmplx Verb >< Cmplx Verb >< P rep Phrase > < P rep Phrase > < P rep >< Cmplx Noun > < Cmplx Noun > < Article >< Noun > < Cmplx Verb > < Verb >< Verb >< Noun Phrase > < Article > < Noun > a the boy girl flower < Verb > < Prep > touches likes sees with 開始記号 < Sentence > 19
導出列 2 G2 から a boy sees が導出できることを示す <Sentence> <Norn-Phrase><Verb-Phrase> <Cmplx-Noun><Verb-Phrase> <Article><Noun><Verb-Phrase> a <Noun><Verb-Phrase> a boy <Verb-Phrase> a boy <Cmplx-Verb> aa boy <Verb> a boy sees 20
練習 G 2 によって 次の文字列が導出できることを 導出列および構文解析木によって示せ (1) the girl touches the boy (2) a girl with a flower likes the boy 21
CFGの形式的定義例 G 1 G1 = ({ A, B}, {0, 1, ε}, { A 0A1, A B, B ε}, A) G 2 G 2 = ( V, Σ, R, < Sentence > ) ただし V = { < Sentence >, < Noun Phraes >, < Verb Phrase >, < P r ep Phrase >, < Cmplx Noun >, < Cmplx Verb >, < Article >, < Noun >, < Verb >, < Pr ep > } Σ= {,,, abc, z,( スペース ) } R は前述の規則の集合 22
曖昧性 CFGにおいて 異なった構文解析木を持つにもかかわらず 同じ文字列を生成することがある このように 2つ以上の構文解析木を持つような文字列を生成できるとき その CFG は曖昧であるといわれる 23
曖昧な CLG 例 G3 = ( V, Σ, R, < Exp > ) V = { < Expr > } Σ= { a, +,,(,)} R = { < Expr > < Expr > +< Expr > < Expr > < Expr > ( < Expr > ) a } <Expr> <Expr> <Expr> <Expr> <Expr> <Expr> <Expr> <Expr> <Expr> <Expr> a + a a a + a a 24
練習 G によって 次の文字列が生成できる 2 the girl touches the boy with the flower この文字列の構文解析木を 2 つ示すことによって が曖昧であることを示せ G 2 25
曖昧性の除去 簡単な数式を生成する CLG G 3 は曖昧であった ここでは 簡単な数式を生成する曖昧でないCLG G 4 を示す G4 = ( V, Σ, R, < Exp > ) V = { < Expr ><, Term ><, Factor > } Σ = { a, +,,(,)} R = { < Expr > < Expr > +< Term >< Term >, < Term > < Term > < Factor >< Factor >, < Factor > ( < Expr > ) a } 26
<Expr> <Term> <Term> <Expr> <Factor> <Expr> <Expr> <Term> <Term> <Term> <Expr> <Term> <Term> <Factor> <Factor> <Factor> <Factor> <Factor> <Factor> a + a a ( a + a ) a 27
本質的に曖昧な CFL 曖昧な文法に対して 同じ言語を生成する曖昧でない文法を構成できることがある ( 例えば G 3 と G 4 ) しかし 曖昧な文法によってのみ生成可能な言語が存在する 次の言語は CFL であるが 曖昧な文法だけからしか生成できない ( このような言語は本質的に曖昧と呼ばれることがある ) i j k {0 1 2 i = jまたはj = k} 28
CFG の応用 プログラミング言語の文法定義 C 言語の文法定義の一部 statement: lableled-statement expression-statement compound-statement selection-statement statement iteration-statement jump-statement selection-statement: if( expression ) statement if( expression ) statement else statement switch ( expression ) statement 斜体 : 非終端記号 立体 : 終端記号 29