言語理論とオートマトン

　集合の記法

内延記法、外延記法、⊆、∈、∪、∩、^C、－

　文字列と言語

アルファベット、演算

　文法とは

生成装置、終端記号と非終端記号、導出

　文法の階層

正則文法、文脈自由文法、文脈依存文法、句構造文法

　オートマトンとは

認識装置、遷移関数、時点表示、受理、非決定性オートマトン

　オートマトンの階層

有限オートマトン、プッシュダウンオートマトン、線形有界オートマトン、チューリング機械

　文法とオートマトンの対応

　正則言語

正則文法、有限オートマトン

　閉じている演算

　様々な特徴づけ

　非正則言語

　正規表現

　検索

文学作品の分析

　検索と置換

　テキスト処理(LEX)

動作付き正規文法(lex)

　字句解析(LEX)

　文脈自由文法

　導出木とあいまい性

　プッシュダウオートマトン

　閉じている演算

代入

　様々な特徴づけ

反復補題、Dyck言語

　非文脈自由言語

　決定性プッシュダウンオートマトン

　構文解析(yacc)

動作付き文脈自由文法

　XMLと文書型の定義

　チューリング機械

　句構造文法

　帰納的可算言語

　文脈依存言語

　TMとコンピュータ

　計算可能性

　問題とは

　停止問題

　Riceの定理

　P問題

　NP問題

　NP完全問題

　公開鍵暗号と電子署名

ゼロ知識証明