計算理論の基礎 [1] ２章

Information

ver	date	memo
1.0	2013/06/02	first

始めに

http://www.amazon.co.jp/計算理論の基礎-原著第2版-1-オートマトンと言語-Michael-Sipser/dp/4320122070
上記の本の勉強の際のメモをまとめる。

計算理論の基礎（原著第２版）[１]オートマトンと言語

pp126-127のChomsky標準形化の詳細
[1]
S -> ASA | aB
A -> B | S
B -> b | e

[2] 新しい開始変数追加
S0 -> S
S -> ASA | aB
A -> B | S
B -> b | e

[3] e規則 B -> e を削除
S0 -> S
S -> ASA | aB | a (aB => ae => a)
A -> B | S | e (B => e)
B -> b

[4] e則 A -> e を削除
S0 -> S
S -> ASA | aB | a | SA | AS | S (ASA => ASe => AS, ASA => eSA => SA, ASA => eSe => S)
A -> B | S
B -> b

[5] 単位規則 S -> S を削除
S0 -> S
S -> ASA | aB | a | SA | AS
A -> B | S
B -> b

[6] 単位規則 S0 -> S を削除
S0 -> ASA | aB | a | SA | AS (S0 -> Sを削除により S -> ASA | aB | a | SA | AS を追加)
S -> ASA | aB | a | SA | AS
A -> B | S
B -> b

[7] 単位規則 A -> B を削除
S0 -> ASA | aB | a | SA | AS
S -> ASA | aB | a | SA | AS
A -> S | b (A -> Bを削除により B -> b を追加)
B -> b

[8] 単位規則 A -> S を削除
S0 -> ASA | aB | a | SA | AS
S -> ASA | aB | a | SA | AS
A -> b | ASA | aB | a | SA | AS
B -> b

[9] S0 -> ASA の置き換え(長さ3以上の規則なので)
S0 -> AA1 | aB | a | SA | AS (ASA = AA1に置き換え, SAは長さ2なのでそのまま)
S -> AA1 | aB | a | SA | AS (ASA = AA1に置き換え, SAは長さ2なのでそのまま))
A -> b | AA1 | aB | a | SA | AS
A1 -> SA
B -> b

[10] U -> a を追加(長さ2の規則の終端記号置き換え)
S0 -> AA1 | UB | a | SA | AS (U = aによる置き換え)
S -> AA1 | UB | a | SA | AS (U = aによる置き換え)
A -> b | AA1 | UB | a | SA | AS (U = aによる置き換え)
A1 -> SA
U -> a
B -> b

プッシュダウンオートマトン(Chap2.2, p127)

理解するべきこと

有限オートマトン(FDA/NFA)の拡張
Pushdown Automaton : PDA
スタックの概念
無限の容量のスタックを（１つ）持つ
無限のスタックを持つので、DFA/NFAで認識出来なかった $\{0^n1^n | n \ge 0\}$ を認識できる事。
文脈自由文法と能力の点で等価
(L(M), N(M), L(G)関連の話)

定理メモ

[Th2.20] $PDA \Leftrightarrow CFL$
[Lem2.21] $PDA \Leftarrow CFL$
[Lem2.22] $PDA \Rightarrow CFL$
$[Lem2.21], [Lem2.22] \vdash [Th2.20]$
$[Claim2.30], [Claim2.31] \vdash [Lem2.22]$

参考リンク

http://ja.wikipedia.org/wiki/プッシュダウン・オートマトン
 http://www.jaist.ac.jp/~uehara/course/2009/ti118/13pda-nm.pdf
http://kurt.scitec.kobe-u.ac.jp/~kikyo/lec/09/automaton/pda.pdf

非文脈自由言語(Chap2.3, p144)

Th2.34 (p145-)

p145

bを規則の右辺にある文字の最大数（少なくとも２以上）

S -> aS | Sb | a
としたら5なのか？
（Sは変数、a,bは終端文字）

p146

生成された文字列の長さが少なくとも $b^h + 1$ ならば、構文解析木の高さは少なくとも $h + 1$

('cuz) 構文解析木の高さが、高々h -> 生成された文字列の長さは高々 $b^h$
=> 文字列の長さが $b^h$ のとき、木の高さがh
文字列の長さが $b^h$ のとき、木の各節点は葉を持てないので
文字列の長さが $b^h + 1$ のとき、木の高さはh+1にならざるを得ない。
という事かな？

$b^{|V|+1} \gt b^{|V|}+1$

('cuz) $b^{|V|+1} = bb^{|V|}$
=> $b^{|V|+1} \ge 2b^{|V|}$ (bは少なくとも2以上なので）
=> $b^{|V|+1} \ge b^{|V|} + b^{|V|}$
=> $b^{|V|+1} \gt b^{|V|} + 1$ ( $b^{|V|} \gt 1$ なので）