形式文法 - 鳥取大学

形式言語 と オートマト
第13回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
本日の予定
形式言語とオートマト
正規文法と有限オートマトンの対
応
は
(有限状態言語)
を生成し、
は
を識別する
形式言語とオートマト
(有限状態言語)
正規文法と有限オートマトンの対
応
オートマトンの遷移規則
q0
a
q1
q1
q2
S1  aS2
q0
S2  aS0
a
q2
q2
a
S0  aS1
S2  a
a
オートマトンの遷移規則 δ(q,a)=p があるときは、
文法の置換規則 Q→aP が対応。
但しpが終状態ならば Q→a が対応。
形式言語とオートマト
正規文法と有限オートマトンの対
応
S0  aS1
q0
S1  aS2
a
S 2  aS0
S2  a
L={a3n}を生成する文法
q1
a
a
q2
L={a3n}を受理するFSA
S0  aS1  aaS 2  aaaS 0  aaaaS 1  aaaaaS 2  aaaaaa
形式言語とオートマト
対応:文法~言語~オートマト
ン
オートマトン(左)と文法(右)の対応する階層性
FSA
正規文法
PDA
文脈自由文法
LBA
文脈依存文法
TM
句構造文法
形式言語とオートマト
正規表現による正規言語の表現
正規表現に書き換えると?
L = {a3n | n>=0} = {aaa}*
L = {an | n>=0} = {a}*
L={ab,ba} ={ab} U {ba}
L={aa}{a,b}*{bbb}
形式言語とオートマト
L = (a3)*
L = a*
L=ab+ba
L=a2(a+b)*b3
文脈自由文法
により生成される
オートマトンでなく
とき、
G=(V,T,S,P)
V={A,B,C},
T={0,1},
S=A,
P ={A→BC, A→BAC, B→0, C→1}
L={01, 0011, 000111, 00001111,…}
形式言語とオートマト
これは有限状態言語でない
有限状態オートマトンを作ろうとすると
無限個の状態が必要。
0がn個並んだ後に1が同じ個数n個並ぶように
しようとすると、
無限集合ゆえ、
。
があるが、
。
1の部分に作っても同じ。
0と1にまたがると結果として
。
形式言語とオートマト
CFGの例
問
が生成する言語は?
答
R
L={xx |xは{0,1}*の元,|x|>0}
形式言語とオートマト
注
意
点
は間違い
例えば
も生成
LはCFGでは不可
→
形式言語とオートマト
閉
包
性
• 全てのクラスi-0,1,2,3に属する言語は、和、連結、*
に対して
• 文脈自由言語は補集合や交わりの
• 交わりはドモルガンにより補集合と和で書けるから、
。
。
。
• 正規言語は
。
• Type0は
。
• Type1は補集合の元で閉じることが1988判明した。
(Neil Immerman、SIAM J.Computing vol.17-5)
形式言語とオートマト
閉
包
1.
性
は、
、
、
、などにおいて
2.
は
に於いて
よって
に於いても
反例は
、
において二つの積集合は
であるが、
形式言語とオートマト
、
、
、
Chomsky標準形
プロダクションルールが
, または,
(ここでSは開始記号,A,B,Cは変数aは終端記号)
任意の文脈自由文法Gに対して
する
形式言語とオートマト
Greibach標準形
生成規則が A→aα の形
(Aは非終端記号、aは終端記号、
αは終端記号と非終端記号からなる列)
形式言語とオートマト