スライド 1

形式言語とオートマト
第8回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
本日の予定1
形式言語とオートマト
「有限状態言語＝正規言語の生成規則」
としての正規文法
形式言語とオートマト
言語の生成装置としての形式文法
遷移規則：δ(p,a)=q
状態pにいて文字aを読めば
状態qに移る
p
a
q
状態pにいて文字aを出力し、状態qに移る
Sp  aSq Sp = それまでの文生成の経過を記憶
aを出力 = Sqでその結果の経過を記憶
S a
q
遷移先が受理状態ならそこでおしまい
形式言語とオートマト
言語の生成装置としての形式文法
S 0  aS1
S1  aS2
S2 → aS0
S2  a
L={a3n}を生成する文法
q0
a
q1
a
a
q2
L={a3n}を受理するFSA
S0  aS1  aaS2  aaaS0  aaaaS1  aaaaaS2  aaaaaa
形式言語とオートマト
文
法
文法(grammar)
G  N, , P, S0 
非終端記号(nonterminal)
N  {S0 , S1 , S2 }
終端記号(terminal)
  {a}
生成規則(production rule) P  {p 0, p1 , p 2 , p 3 , p 4 }
初期記号(initial symbol)
形式言語とオートマト
S0
対応：文法～言語～オートマト
ン
オートマトン（左）と文法（右）の対応する階層性
FSA
正規文法
PDA
文脈自由文法
LBA
文脈依存文法
TM
句構造文法
形式言語とオートマト
文法の種類
４つの言語のクラスの関係
形式言語とオートマト
文法の種類
４つの言語のクラスの関係
G1=<{S},{a,b},{S→aS, S→bS, S→a, Sb,},S>
から生成する言語
L(G1)={a,b}
形式言語とオートマト
＋
文法の種類
G2=<{S},{a,b},{S
→ aSb, S → ab},S>
４つの言語のクラスの関係
から生成する言語
L(G2)={an,bn| n≧1 }
形式言語とオートマト
G3=<{S},{a,b},
{S→aSBC aB→ab
文法の種類
S→aBC bB→bb
が生成する言語
CB→AB bC→bc
n n n
L(G3)={a b c | n≧1}
AB→AC cC→cc
４つの言語のクラスの関係
AC→BC},
S>
形式言語とオートマト
文法の種類
４つの言語のクラスの関係
??????
形式言語とオートマト
文法の種類
４つの言語のクラスの関係
形式言語とオートマト
文法の種類＝まとめ＝
形式文法
書き換え規則α→β上の制限
正則文法（正規文法）
（3型）
A→aBまたはA→aという形（文字aを読んでAに対応する状態か
らBに対応する状態に遷移する有限状態オ-トマトンに対応する）
ここで，A,B∈N，a∈T, 開始記号S
文脈自由文法
(２型）
A→βという形をしている。ここで，A∈N, β∈(N∪T)*
(文脈に依存することなく変数Aを単独で置き換えることができる）
文脈依存文法
(１型)
γ1Aγ2→γ1βγ2，ここで，A∈N，γ1,γ2∈(N∪T)*，β∈(N∪T)+
(別の定義としては，|左辺|≤|右辺|)
句構造文法
(０型）
制限なし
形式言語とオートマト
形式言語とオートマト
文法例2(文脈自由文法)
文法(grammar)
非終端記号(nonterminal)
終端記号(terminal)
生成規則(production rule)
初期記号(initial symbol)
形式言語とオートマト
G  N, , P, S0 
N  {S}
  {a, b}
P  {S  aSa, S  bSb, S  aa, S  bb}
S0  S
文法例2(文脈自由文法)
文法(grammar)
非終端記号(nonterminal)
終端記号(terminal)
生成規則(production rule)
初期記号(initial symbol)
G  N, , P, S0 
N  {S}
  {a, b}
P  {S  aSa, S  bSb, S  aa, S  bb}
S0  S
=導出=
S  aSa  aaSaa  aabSbaa  aabaabaa
L  {ww | w {a, b} }
R
形式言語とオートマト
*
文法例2(文脈自由文法)
文法(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
文法例2(文脈自由文法)
文法(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
=導出=
S  aSa  abSba  abaSaba  abaaSaacaa ba
L  {wcw | w {a, b} }
R
形式言語とオートマト
*
文法例3(文脈自由文法)
文法(grammar)
非終端記号(nonterminal)
終端記号(terminal)
生成規則(production rule)
初期記号(initial symbol)
形式言語とオートマト
G  N, , P, S0 
N  {S}
  {, }
P = {S →< >, S → SS, S →< S >}
S0  S
文法例3(文脈自由文法)
文法(grammar)
非終端記号(nonterminal)
終端記号(terminal)
生成規則(production rule)
初期記号(initial symbol)
G  N, , P, S0 
N  {S}
  {, }
P = {S →< >, S → SS, S →< S >}
S0  S
=導出=
S  S 
S  SS  S  S 
L  {ε，, , , ・・・
形式言語とオートマト
}
小テストです。
形式言語とオートマト

Download Report