PowerPoint プレゼンテーション

形式言語 と オートマトン
第13回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
本日の予定
今日全ての例題は答えを出しません,ノートを取って考えてください.
形式言語とオートマトン
試験の考察点(80%)
1.言語の階層構造:言語とオートマトンの対応関係など
2.有限状態オートマトン
正規表現
3.文脈自由文法のCHOMSKY標準形及び言語導出(2分木)
4.NFAをDFAに書き換えること: アルゴリズム2.1/2.2
5.状態遷移図
形式言語とオートマトン
5字組及び状態遷移表の書き方
試験の考察点
1.言語の階層構造:言語とオートマトンの対応関係など
形式言語とオートマトン
1.言語の階層構造:言語とオートマトンの対応関係など
オートマトン(左)と文法(右)の対応する階層性
FSA
正規文法
PDA
文脈自由文法
LBA
文脈依存文法
TM
句構造文法
形式言語とオートマトン
閉
包
性
• 全てのクラスi-0,1,2,3に属する言語は、和、連結、*
に対して
。
• 文脈自由言語は補集合や交わりの
• 交わりはドモルガンにより補集合と和で書けるから、
。
。
• 正規言語は
。
• Type0は
。
• Type1は補集合の元で閉じることが1988判明した。
(Neil Immerman、SIAM J.Computing vol.17-5)
形式言語とオートマトン
閉
包
1.
性
は、
、
、
、などにおいて
2.
は
に於いて
よって
に於いても
反例は
、
において二つの積集合は
であるが、
形式言語とオートマトン
、
、
、
1.言語の階層構造:言語とオートマトンの対応関係など
例
L  {a b | 1
≦ m ≦ n ≦ 2m}
m n
は
(1)
(3)
言語に属し,
(2)
文法で生成でき,
オートマトンで識別できる.
形式言語とオートマトン
試験の考察点
2.有限状態オートマトン
形式言語とオートマトン
正規表現
2.有限状態オートマトン
正規表現
正規表現に書き換えると?
L = {a3n | n>=0} = {aaa}*
L = (a3)*
L = {an | n>=0} = {a}*
L = a*
L={ab,ba} ={ab} U {ba}
L=ab+ba
L={aa}{a,b}*{bbb}
形式言語とオートマトン
L=a2(a+b)*b3
2.有限状態オートマトン
正規表現
a
有限状態オートマトン
正規表現
a+b
正規表現は
有限状態オートマトン
a,b
形式言語とオートマトン
a*
正規表現
2.有限状態オートマトン
例:
a
b
ε
c
c
D
図示のNFAが受理する言語の正規表現を求めてください
形式言語とオートマトン
試験の考察点
3.文脈自由文法のCHOMSKY標準形及び言語導出(2分木)
形式言語とオートマトン
 どんな文脈自由言語(ただし,εを含まないも
の)も,次の形式の規則のみを使って表せる
ことを示したい
A → BC または A → a、 ただし、A、B、Cは非
終端記号、 aは終端記号である(必要に応じて
変数を増やす)
形式言語とオートマトン
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に変更する
形式言語とオートマトン
Chomsky標準形なら2分木になる
P  {S  AB, A  a, B  b, S  AC, C  SB}
S
aabbの導出木は:
A
C
B
S
A B
a
形式言語とオートマトン
a
b
b
3.文脈自由文法のCHOMSKY標準形及び言語導出(2分木)
例:
文法G=(V,T,P,S), V={A}, T={a,b}, P={A→aAb, A→AA, A→ab},
S={A}によって、abaabb という語が導出される過程はどのようになるか、
空白を埋めよ
A ⇒
(1)
⇒
(2)
⇒(3)
⇒
abaabb
これと同じ言語を生成する別の文法を同等な文法と呼ぶ。上のGと同等で文
法G’をChomsky標準形といい、G’=(V’,T,P’,S)を構成し、abaabbの導出木を作れ
形式言語とオートマトン
試験の考察点
4.NFAをDFAに書き換えること: アルゴリズム2.1/2.2
形式言語とオートマトン
4.NFAをDFAに書き換えること: アルゴリズム2.1/2.2
例:
a
b
ε
c
c
D
図示のNFAと同等なDFAの状態遷移図を描け.
形式言語とオートマトン
試験の考察点
5.状態遷移図
形式言語とオートマトン
5字組及び状態遷移表の書き方
有限オートマトンの5字組み表現
5字組み表現
M= <Q,Σ,δ,q0,F>
形式言語とオートマトン
5.状態遷移図
5字組及び状態遷移表の書き方
例1:
a
b
ε
c
c
D
図示のNFAと同等なDFAを5字組で表せ.また、NFAとDFAの状
態遷移表を描け.
形式言語とオートマトン
5.状態遷移図
5字組及び状態遷移表の書き方
例2:
正規表現b*a(a+b)*bbについてNFAとそれに同等な
DFAの状態遷移表と状態遷移図を作れ.
正規表現分からないと
だめですよ.
形式言語とオートマトン
以上です。
講義pptと小テストの答えはホームページで確認してください:
http://irene.ike.tottori-u.ac.jp/mieko/2014autom.html
形式言語とオートマトン