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.言語の階層構造：言語とオートマトンの対応関係など
例
L  {a b | 1
≦ m ≦ n ≦ 2m}
m n
は
(1)
(3)
言語に属し，
(2)
文法で生成でき，
オートマトンで識別できる．
形式言語とオートマトン
試験の考察点
2.有限状態オートマトン
形式言語とオートマトン
正規表現
2.有限状態オートマトン
正規表現
正規表現に書き換えると？
L = {a3n | n>=0} = {aaa}*
Ｌ = (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標準形なら２分木になる
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字組み表現
M= <Ｑ，Σ，δ，q0，Ｆ>
形式言語とオートマトン
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
形式言語とオートマトン

Download Report