Microsoft PowerPoint - 3.ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 3.ppt [互換モード]"

さやなおとじま
5 years ago
Views:

1 3. プッシュダウンオートマトンと文脈自由文法 1

2 3-1. プッシュダウンオートマトンオートマトンはメモリがほとんど無かったこの制限を除いた機械を考える理想的なスタックを利用できるようなオートマトンをプッシュダウンオートマトン (Push Down Automaton,PDA) という 0 1 入力テープ 1 a スタッb 入力テープを一度走査したあとク2 入力テプを度走査したあとはいならランプ点灯いいえならランプ消灯

3 ック有限制御部タPDA の概略有限制御部読み取りヘッド 0 1 入力テープ b PDA を定める要素スa 入力テープテープに書ける文字有限制御部内部状態初期状態状態変化受理かどうかの判断スタック ( 無限長 ) スタックに書ける文字 3

4 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

5 PDA の図式表現 ( 状態遷移図 ) PDA は状態遷移図で表現できる ( q', t') δ ( q, s, t) のとき入力記号 st, t' q q ' 状態の変化スタックの変化スタック先頭の記号をからへ変化させる t t ' push('): t ε t ' t = pop () : t ε 5

6 PDA の例 B n n = {0 1 n 0} を認識するPDA PDA 例 1 P P ε, ε $ 1 q 1 q 2 0, ε ,0 ε q 4 ε,$ ε q 3 1, 0 ε 6

7 形式的定義 P = ( Q, Σ,Γ, δ, q, F) 1 1 ただし Q= { q1, q2, q3, q4} Σ={0,1} {0,$} ( 状態集合 ) Σ= ( 入力アルファベット ) Γ= ( スタックアルファベット ) F スタックの底を表す特別な記号 q 1 ( 初期状態 ) = { q, q } ( 受理状態 ) 1 4 7

8 δ 状態遷移関数入力 0 1 ε スタック 0 $ ε 0 $ ε 0 $ ε q 1 2 q {( q,0)} {( q, ε )} q {( q, ε)} {( q, ε)} q 4 {( q,$)} この表において空白は空集合 φ を表している 8

9 スPDA の状態遷移 w = 0011 による状態遷移 0, ε 0 0, ε 0 q ε, ε $ 1 q q q 2 タ2 $ 0 ック$ 1, 0 ε q $ q 3 0 $ 1, 0 ε q 3 $ ε,$ ε q 4 9

10 例 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

11 練習 P に対する形式的な定義を求めよまた 2 s = に対するの遷移をスタックの内容と共に示せ P 2 11

12 3-2. 文脈自由文法以前 DFAが認識できる言語のクラス ( 正規言語 ) に対して異なる表現法 ( 正規表現 ) を与えたここでは PDA が認識できる言語のクラス ( 文脈自由言語 ) に対してもう一つの表現法 ( 文脈自由文法 ) を与える 12

13 文脈自由文法とは文法例 G 1 A A B 0 A 1 B ε 導出 A 0 A 1 00 A B ε 文脈自由文法は生成規則あるいは書き換え規則と呼ばれる式の集合で定められる生成規則の左辺は一つの変数 ( 非終端記号 ) であり右辺は変数とアルファベット ( 終端記号 ) の列である文脈自由文法では開始記号から生成規則を基に書き換えられるすべて記号が終端記号になった時点で終了する ( 上の例 G 1 では開始記号は A としている ) 文脈自由文法において終端記号列に変換する過程 ( 生成記号系列 ) を導出という 13

14 CFG のの形式的定義 CFGは C = ( V, Σ, R, S) の4 項組で与えられるここで 1. V は変数 ( 非終端記号 ) と呼ばれる有限集合 2. Σ はアルファベット ( 終端記号 ) と呼ばれ有限集合 Vとは共通部分を持たないつまり V Σ= φ 3. Rは生成規則の有限集合であるただし生成規則の左辺は一つの非終端記号であり右辺は変数と終端記号の文字列からなる * すなわち各生成規則は A V, α ( V + ) として A α と表される 4. S V は開始記号 14

15 導出可能性を表す表現 ( ) * ある系列 α V + に任意回 ( k ( 1) 回 ) の規則の適用で * 系列が得れることを * β ( V + ) α β とも書くすなわち * は α β α = α α α = β のことである 1 2 k 15

16 文脈自由言語 (CFL) 文脈自由文法 (Context-Free Grammar,CFG) で記述できる言語を文脈自由言語 (Context-Free Language,CFL) と呼ぶある文脈自由文法 G に対して G から導出できる言語を LG ( ) と書く 16

17 導出列 G がを導出できることを示す A 0A1 00A11 000A B ε このような生成規則の適用される順序を示したものを導出列とよぶ 17

18 構文解析木文字列に対して導出における生成規則の適用を図式的に表現できるこのような導出過程を表す木状の図形を構文解析木と呼ぶ A A A A B ε

19 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

20 導出列 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

21 練習 G 2 によって次の文字列が導出できることを導出列および構文解析木によって示せ (1) the girl touches the boy (2) a girl with a flower likes the boy 21

22 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

23 曖昧性 CFGにおいて異なった構文解析木を持つにもかかわらず同じ文字列を生成することがあるこのように 2つ以上の構文解析木を持つような文字列を生成できるときその CFG は曖昧であるといわれる 23

24 曖昧な 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

25 練習 G によって次の文字列が生成できる 2 the girl touches the boy with the flower この文字列の構文解析木を 2 つ示すことによってが曖昧であることを示せ G 2 25

26 曖昧性の除去簡単な数式を生成する 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

27 <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

28 本質的に曖昧な CFL 曖昧な文法に対して同じ言語を生成する曖昧でない文法を構成できることがある ( 例えば G 3 と G 4 ) しかし曖昧な文法によってのみ生成可能な言語が存在する次の言語は CFL であるが曖昧な文法だけからしか生成できない ( このような言語は本質的に曖昧と呼ばれることがある ) i j k {0 1 2 i = jまたはj = k} 28

29 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

Microsoft PowerPoint - 1.ppt [互換モード]

Microsoft PowerPoint - 1.ppt [互換モード] 第回オートマトンと正規表現 8//5( 火 ) 履修にあたって 8 年度情報数理学 8 年度大学院奇数セメスター ( 前期 ) 開講教室 : K6 大学院棟 D6( 次回から ) 担当時限 : 火曜日時限 (:5-:) 草苅良至講義予定計算機のいろいろな理論モデル言語理論計算の限界計算量理論問題の難しさ現実問題と計算アルゴリズム論参考書. Sipser 著計算理論の基礎共立出版