形式言語とオートマトン2009
ー第10日目ー
東京工科大学
コンピュータサイエンス学部
亀田弘之
1.
2.
3.
4.
曖昧性
標準形
自己埋め込み性
その他
– 構文解析プログラム例
– ポンプの定理の証明
１．曖昧性
• 構文の曖昧性
• 文法の曖昧性（曖昧な文法）
• 言語の曖昧性（曖昧な言語）
例3
前回の授業のスライド
• 文法 ： G=（ Vn, Vt, P, S ）：
– ただし、
• Vn={ E, T, F }
• Vt={ a, +, ×, (, ) }
• P={ E→E+T | T
T →T×F | F
F →( E ) | a
}
• S={ E }
• 言語 ：L=L(G)は具体的にどうなる？
4
問
前回の授業のスライド
• a+a×a の導出木を示せ。
• (a+a)×a の導出木を示せ。
5
例４
前回の授業のスライド
• P={
E → E+E | E×E | ( E ) | a
}
曖昧な文法
6
２．CFGの標準形
• Chomskyの標準形
• Greibachの標準形
Chomskyの標準形
• 任意のCFGにおける書き換え規則群Pは、
A→BC または A→a という形だけで表現で
きる。
Greibachの標準形
• 任意のCFGにおける書き換え規則群Pは、
A→aα という形だけで表現できる。ただし、
X∈Vn, a∈Vt, α∈Vn*。
Chomskyの標準形への変換方法
自己埋め込み性
• Ｃｆｇが自己埋め込みとは、
A→aAb
となるような非終端記号Aが存在すること。
ただし、a,bは空でない記号列。
ポンピングの補題
• 言語LはDFA M により受理されるとする。このと
きある定整数nが存在して、z∊L, |z| ≧n なるzは、
z=uvw, |uv| ≦n, |v|≧1
のように分解され、かつ、
uviw ∊ L
となる。
（この補題はさまざまな定理の証明に役立つ。）

形式言語とオートマトン2009 ー第10日目ー