形式言語 と オートマト 第9回 鳥取大学工学研究科 情報エレクトロニクス専攻 田中美栄子 本日の予定1 形式言語とオートマト 文法例1(文脈自由文法) 文法(grammar) 非終端記号(nonterminal) 終端記号(terminal) 生成規則(production rule) 初期記号(initial symbol) G N, , P, S0 N {S } {a, b, c} P {S aSb, S ab, 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 を生成する文脈自由文法を構成しなさい 形式言語とオートマト 文法例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 → aAa, A → B, B → bBa, B → ba} =導出例= S ⇒ aAa ⇒ abBaa ⇒ abbaaa 形式言語とオートマト 形式言語とオートマト 本日の予定2 形式言語とオートマト 文脈自由文法 プロダクションルールPの要素がすべて 1変数 → w ここでwは ・変数 ・定数 ・変数と定数の組み合わせ のいずれかである場合、文脈自由文法と呼ぶ 生成される言語は文脈自由言語 形式言語とオートマト 例1: 先に並んだ変数の数と等しい 数の文字が後に並ぶ文字列の生成 S0 aS1 の形の規則(正規文法)では不可能 G=<N,Σ,P,S> {a , b} N {S} P {S aSb , S ab} S0 S S aSb aaSbb aaabbb L1 {a b } n n 形式言語とオートマト 例2: 対応する括弧の列を生成 S0 aS1 の形の規則(正規文法)では不可能 G=<N,Σ,P,S> N {S} {a , b} S0 S P {S aSb, S ab, S SS} S aSb aSSb aabSb aabaSbb aabaabbb L 2 {aの数= bの数 , aの後から bが出る } 形式言語とオートマト 例3: 2変数の数が等しい文字列生 成 S0 aS1 の形の規則(正規文法)では不可能 G=<N,Σ,P,S> N {S, A, B} {a , b} S0 S P {S aB, S bA, A bAA, A a, B aBB, B bS, A aS, B b} S aB aaBB aaaBBaBB aaabbabb L3 {aと bから作られる文字列, aの数=bの数} 形式言語とオートマト 文脈自由文法は木構造で書ける • A→aBb, A→a, B →c A B a 形式言語とオートマト c b 2文木(binary tree)にする • Chomsky 標準形 • A→BC の形、または • A→a の形 にする • (必要に応じて変数を増やす) 形式言語とオートマト 例1 L {a b } n n • 下記の生成規則をChomsky標準形にする P {S aSb , S ab} P {S AB, A a, B b, S AC, C SB} 形式言語とオートマト 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 小テストです。 形式言語とオートマト
© Copyright 2025 ExpyDoc