日本語の著書だが"Archimage Garret’s Apprenticeship: Adventures in Automata and Formal Languages"という英語タイトルがいい
文系理系という非科学的で無意味なカテゴライズに縛られている方はこの本が文学部文学科を卒業された方が書かれたことをどのように思うのであろうか。僕がつぎに本を書くとしたらこのような本が書きたい。まぁ、これが枷になってもう20年近く本を出していない。まぁ、書きたくなるようなワクワクする技術に出合っていないからでもあるけど。
逆に言えば、読者層が限られる書籍をよく出版し、続編まである。
またまたチャムスキー。
遺跡(オートマトン)には白と黒のとびらのついた部屋の集まりから構成されている。
遺跡の各部屋が状態、入口の部屋が初期状態、出口の部屋が終了状態、扉が入力される記号
扉は古代語(形式言語)の文法に基づいて開けることができる。
〇と●の二つの文字からなる文字列の集合が形式言語
・「計算」とはそもそも何なのか？
・計算機械にできることと、できないことの境目はどこにあるのか？
・人間の脳を一種の「計算機械」と見なした場合、私たちの持つ言語能力をどのように説明することができるか？
有限オートマトン 正則言語 3型文法(正則文法)
プッシュダウンオートマトン 文脈自由言語 2型文法(文脈自由文法)
線形拘束オートマトン 文脈依存言語 1型文法(文脈依存文法)
1章、２章 ・正則言語と有限オートマトン
古代ルル語系→正則言語
3章 有限オートマトンの決定性・非決定性と正則表現
決定性オートマトン→2章までの遺跡
非決定性オートマトン→3章の遺跡
讒言→正則表現
4章 有限オートマトンと実際の機械
奇妙な屋敷→有限オートマトン
5章、6章 文脈自由言語とプッシュダウンオートマトン
古代クフ言語系→文脈自由言語に属する言語のうち正則言語でないもの
プッシュダウンオートマトン→文脈自由言語のクラスに属する言語に含まれる文字列
透明な筒→スタック
試し部屋→第一古代クフ語
妹の祠→第三十三古代クフ語
7章、8章 正則言語と文脈自由言語に対する反復補題
正規言語の反復補題
①y ≠ ε
②|xy|≦ n
③すべてのk ≧ 0に対して、xy^k・zもまたLに属する
文脈自由言語の反復補題
①|vwx| ≦ n
②vx ≠ ε vとxは反復部分であり、反復部分の少なくとも一方は空ではない
③任意のiに対して、uv^iwx^iy ∈Lすなわち、二つの列vとxは、連動して0回以上の任意の回、反復でき、得られた列は再びLに属する。
「省き」と「延ばし」が使える部分が正規言語の反復補題のy、文脈自由言語の反復補題のvとx
9章、10章 文脈自由文法とプッシュダウンオートマトンの透過性
11章、12章 文脈自由言語の統語解析
偽クフ言語→文脈自由言語
13章 文脈依存言語と線形拘束オートマトン・チューリングマシン
第一古代セティ語→文脈依存言語
14章 万能チューリングマシン
ソアの塔→万能チューリングマシン
15章、16章 対角線言語と決定不能性
