形式言語 と オートマト 第9回 鳥取大学工学研究科 情報エレクトロニクス専攻 田中美栄子 本日の予定1 形式言語とオートマト 文法例1(文脈自由文法) 文法(grammar) 非終端記号(nonterminal) 終端記号(terminal) 生成規則(production rule) 初期記号(initial symbol) G N, , P, S0 N {S } {a, b, c} P {S aSa, S bSb, S c} S0 S この文法が生成する言語は? 形式言語とオートマト 文法例1(文脈自由文法) 文法(grammar) 非終端記号(nonterminal) 終端記号(terminal) 生成規則(production rule) 初期記号(initial symbol) G N, , P, S0 N {S } {a, b, c} P {S aSa, S bSb, S c} S0 S =導出例= S ⇒ aSa ⇒ abSba ⇒ abaSaba ⇒ abacaba L {wcw | w {a, b} } R 形式言語とオートマト * 文法例2(文脈自由文法) 言語 L {a b | 1 ≦ m ≦ n ≦ 2m} m n を生成する文脈自由文法を構成しなさい 形式言語とオートマト 文法例2(文脈自由文法) 言語 L {a b | 1 ≦ m ≦ n ≦ 2m} m n を生成する文脈自由文法を構成しなさい =解答= G {S}, { a, b}, P, S P = {S → aSb, S → aSbb, S → ab, S → abb} 形式言語とオートマト 文法例2(文脈自由文法) 言語 L {a b | 1 ≦ m ≦ n ≦ 2m} m n を生成する文脈自由文法を構成しなさい G =< {S}, { a , b}, P, S} P = {S → aSb, S → aSbb, S → ab, S → abb} =導出例= S ⇒ aSb ⇒ aaSbbb ⇒ aaabbbb 形式言語とオートマト 形式言語とオートマト 文法例3(文脈自由文法) 言語 L {a b a | i, j, k ≧1, i j k} i j k を生成する文脈自由文法を構成しなさい. 形式言語とオートマト 文法例3(文脈自由文法) 言語 L {a b a | i, j , k ≧1, i j k} i j k を生成する文脈自由文法を構成しなさい. =解答= G =< {S, A, B},{a , b}, P, S > P = {S → aAa, A → bBa , B → ba , A → ba} 形式言語とオートマト 文法例3(文脈自由文法) 言語 L {a b a | i, j, k ≧1, i j k} i j k を生成する文脈自由文法を構成しなさい. P {S → aAa, A → bBa, B → ba, A → ba} =導出例= S ⇒ aAa ⇒ abBaa ⇒ abbaaa 形式言語とオートマト 形式言語とオートマト 本日の予定2 形式言語とオートマト 文脈自由文法 プロダクションルールPの要素がすべて 変数1個→w の形:Wは変数,定数,変数と定数で作る文字列 の場合、文脈自由文法と呼ぶ 生成される言語は文脈自由言語 形式言語とオートマト 同等な複数の異なる文法が作れ る P1 = { S → BSC, S → BC, B → b, C → c} P2= {S → bSc, S → bc} P1とP2は同等 どんな文脈自由言語(ただし,εを含まないも の)も,次の形式の規則のみを使って表せる ことを示したい A → BC または A → a、 ただし、A、B、Cは 非終端記号、 aは終端記号である(必要に応じ て変数を増やす) 形式言語とオートマト 無用な記号の除去:開始記号から終端記号列 への導出に出現しない変数や終端記号の除去 ε-規則の除去:A → εの形式の規則の除去 単位規則の除去:A → Bの形式の規則の除去 S0 aS1 の形の規則(正規文法)では不可能 形式言語とオートマト 例1: 先に並んだ変数の数と等しい数の 文字が後に並ぶ文字列の生成 G N, , P, S0 N {S } {a, b} P {S aSb, S ab} S0 S S aSb aaSbb a Sb a 3 生成される言語: 形式言語とオートマト 3 L {a nb n | n 1} n 1 Sb n 1 a b n n G N, , P, S0 N {S } {a, b} P {S aSb, S ab} S0 S S aSb S ASB, A a, B b, C SB, S AC S ab S AB 規則を:A → BCまたはA → aに変更する 形式言語とオートマト G N, , P, S0 G N, , P, S0 N {S } N {S,A,B,C} {a, b} {a, b} P {S aSb, S ab} P {S AB, A a, B b, S AC , C SB} S0 S S0 S 形式言語とオートマト 文脈自由文法は木構造で書ける • A→aBb, A→a, B →c A B a 形式言語とオートマト c b Chomsky標準形なら2分木になる 形式言語とオートマト Chomsky標準形なら2分木になる P {S aSb, S ab} P {S AB, A a, B b, S AC , C SB} S S A C B S S A B a a b b 形式言語とオートマト a a b b Chomsky標準形なら2分木になる S 木の深さは最大でも A 文字列の長さである C B S A B a 形式言語とオートマト a b b Chomsky標準形は一つではない P {S AB, A a, B b, S AC , C SB} これとは異なる、同等な文法を作ろう • その文法と,元の文法で、それぞれaaabbb を導出せよ 形式言語とオートマト P {S AB, A a, B b, S AC , C SB} S C P {S AB, A a, B b, S CB, C AS} S C S S C S A A A B B B a a a b b b C S A A A B B B a a a b b b 形式言語とオートマト 例2 G=<N,Σ,P,S> N {S} {a, b} S0 S P {S aSb, S ab, S SS} S aSb aSSb aabSb aabaSbb aabaabbb L {w | # a(w) # b(w) ≧1} 形式言語とオートマト 例2 G N, , P, S0 N {S } G N, , P, S0 N {S,A,B,C} aabaabbbの導出木を示せ {a, b} {a, b} P {S aSb, S ab S SS } S0 S 形式言語とオートマト P {S SS , S AB, A a, B b, S AC , C SB} S0 S 例2 aabaabbbの導出木を示せ P {S aSb, S ab S SS } S C S S S S S S S C S S a a baa b b b 形式言語とオートマト A A B AA B B B a a b a a b b b 小テストです。 形式言語とオートマト
© Copyright 2024 ExpyDoc