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

形式言語とオートマトン2010
ー第10日目ー
東京工科大学
コンピュータサイエンス学部
亀田弘之
今日も言語について
理解を深めましょう。
• 言語とは何か。
• 言語とは以下に定義されるものなのか。
• 言語とは．．．
今日の内容
1.
2.
3.
4.
曖昧性
標準形
自己埋め込み性
その他
– (構文解析プログラム例)
– (ポンプの定理の証明)
１．曖昧性
• “あいまいせい”と読む。
• 曖昧性（日本語）にはいろいろな意味がある。
– Ambiguity
– Vague
– Fuzzy など
形式言語で取り上げる曖昧性とは、一般に
ambiguity（多義性）のことである。
vague
fuzzy
１．曖昧性
• 構文の曖昧性
• 文法の曖昧性（曖昧な文法）
• 言語の曖昧性（曖昧な言語）
例：
賢いボクの友達
美しい水車小屋の娘
青いルビーのケース
• 真っ赤なネギ入りのラーメン
例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)は具体的にどうなる？
11
問
前回の授業のスライド
• a+a×a の導出木を示せ。
• (a+a)×a の導出木を示せ。
12
例４
前回の授業のスライド
• P={
E → E+E | E×E | ( E ) | a
}
曖昧な文法
13
２．CFGの標準形
• Chomskyの標準形
• Greibachの標準形
Chomskyの標準形
• 任意のCFGにおける書き換え規則群Pは、
A→BC または A→a という形だけで表現で
きる。
Greibachの標準形
• 任意のCFGにおける書き換え規則群Pは、
A→aα という形だけで表現できる。ただし、
X∈Vn, a∈Vt, α∈Vn*。
Chomskyの標準形への変換方法
S -> ASA |aB
A -> B|S
B -> b|ε
自己埋め込み性
• Ｃｆｇが自己埋め込みとは、
A→aAb
となるような非終端記号Aが存在すること。
ただし、a,bは空でない記号列。
ポンピングの補題
• 言語LはDFA M により受理されるとする。このと
きある定整数nが存在して、z∊L, |z| ≧n なるzは、
z=uvw, |uv| ≦n, |v|≧1
のように分解され、かつ、
uviw ∊ L
となる。
（この補題はさまざまな定理の証明に役立つ。）

Download Report