close
1.

図書

図書
A.V.エイホ, J.E.ホップクロフト, J.D.ウルマン共著 ; 野崎昭弘, 野下浩平訳者代表
出版情報: 東京 : サイエンス社, 1977.10  2冊 ; 22cm
シリーズ名: サイエンスライブラリ情報電算機 ; 35-36
所蔵情報: loading…
2.

図書

図書
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
出版情報: Reading, MA : Addison-Wesley, 1974  x, 470 p. ; 24 cm
シリーズ名: Addison-Wesley series in computer science and information processing
所蔵情報: loading…
3.

図書

図書
John E. Hopcroft, Jeffrey D. Ullman
出版情報: Reading, Mass. : Addison-Wesley Pub. Co., c1969  vii, 242 p. ; 24 cm
シリーズ名: Addison-Wesley series in computer science and information processing
所蔵情報: loading…
4.

図書

図書
by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
出版情報: Boston : Pearson Addison-Wesley, c2007  xvii, 535 p. ; 24 cm
所蔵情報: loading…
目次情報: 続きを見る
Automata: The Methods and the Madness / Chapter 1:
Why Study Automata Theory / 1.1:
Introduction to Formal Proof / 1.2:
Additional Forms of Proof / 1.3:
Inductive Proofs / 1.4:
The Central Concepts of Automata Theory / 1.5:
Summary of Chapter 1 / 1.6:
Gradiance Problems for Chapter 1 / 1.7:
References for Chapter 1 / 1.8:
Finite Automata / Chapter 2:
An Informal Picture of Finite Automata / 2.1:
Deterministic Finite Automata / 2.2:
Nondeterministic Finite Automata / 2.3:
An Application_ Text Search / 2.4:
Finite Automata With EpsilonTransitions / 2.5:
Summary of Chapter 2 / 2.6:
Gradiance Problems for Chapter 2 / 2.7:
References for Chapter 2 / 2.8:
Regular Expressions and Languages / Chapter 3:
Regular Expressions / 3.1:
Finite Automata and Regular Expressions / 3.2:
Applications of Regular Expressions / 3.3:
Algebraic Laws for Regular Expressions / 3.4:
Summary of Chapter 3 / 3.5:
Gradiance Problems for Chapter 3 / 3.6:
References for Chapter 3 / 3.7:
Properties of Regular Languages / Chapter 4:
Proving Languages Not to Be Regular / 4.1:
Closure Properties of Regular Languages / 4.2:
Decision Properties of Regular Languages / 4.3:
Equivalence and Minimization of Automata / 4.4:
Summary of Chapter 4 / 4.5:
Gradiance Problems for Chapter 4 / 4.6:
References for Chapter 4 / 4.7:
Context-Free Grammars and Languages / Chapter 5:
Context-Free Grammars / 5.1:
Parse Trees / 5.2:
Applications of Context-Free Grammars / 5.3:
Ambiguity in Grammars and Languages / 5.4:
Summary of Chapter 5 / 5.5:
Gradiance Problems for Chapter 5 / 5.6:
References for Chapter 5 / 5.7:
Pushdown Automata / Chapter 6:
Definition of the Pushdown Automaton / 6.1:
The Languages of a PDA / 6.2:
Equivalence of PDA's and CFG's / 6.3:
Deterministic Pushdown Automata / 6.4:
Summary of Chapter 6 / 6.5:
Gradiance Problems for Chapter 6 / 6.6:
References for Chapter 6 / 6.7:
Properties of Context-Free Languages / Chapter 7:
Normal Forms for Context-Free Grammars / 7.1:
The Pumping Lemma for Context-Free Languages / 7.2:
Closure Properties of Context-Free Languages / 7.3:
Decision Properties of CFL's / 7.4:
Summary of Chapter 7 / 7.5:
Gradiance Problems for Chapter 7 / 7.6:
References for Chapter 7 / 7.7:
Introduction to Turing Machines / Chapter 8:
Problems That Computers Cannot Solve / 8.1:
The Turing Machine / 8.2:
Programming Techniques for Turing Machines / 8.3:
Extensions to the Basic Turing Machine / 8.4:
Restricted Turing Machines / 8.5:
Turing Machines and Computers / 8.6:
Summary of Chapter 8 / 8.7:
Gradiance Problems for Chapter 8 / 8.8:
References for Chapter 8 / 8.9:
Undecidability / Chapter 9:
A Language That Is Not Recursively Enumerable / 9.1:
An Undecidable Problem That Is RE / 9.2:
Undecidable Problems About Turing Machines / 9.3:
Post's Correspondence Problem / 9.4:
Other Undecidable Problems / 9.5:
Summary of Chapter 9 / 9.6:
Gradiance Problems for Chapter 9 / 9.7:
References for Chapter 9 / 9.8:
Intractable Problems / Chapter 10:
The Classes P and NP / 10.1:
An NP-Complete Problem / 10.2:
A Restricted Satisfiability Problem / 10.3:
Additional NP-Complete Problems / 10.4:
Summary of Chapter 10 / 10.5:
Gradiance Problems for Chapter 10 / 10.6:
References for Chapter 10 / 10.7:
Additional Classes of Problems / Chapter 11:
Complements of Languages in NP / 11.1:
Problems Solvable in Polynomial Space / 11.2:
A Problem That Is Complete for PS / 11.3:
Language Classes Based on Randomization / 11.4:
The Complexity of Primality Testing / 11.5:
Summary of Chapter 11 / 11.6:
Gradiance Problems for Chapter 11 / 11.7:
References for Chapter 11 / 11.8:
Index
Automata: The Methods and the Madness / Chapter 1:
Why Study Automata Theory / 1.1:
Introduction to Formal Proof / 1.2:
5.

図書

図書
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
出版情報: Boston : Addison-Wesley, c2001  xiv, 521 p. ; 25 cm
所蔵情報: loading…
目次情報: 続きを見る
Automata: The Methods and the Madness / Chapter 1:
Why Study Automata Theory / 1.1:
Introduction to Formal Proof / 1.2:
Additional Forms of Proof / 1.3:
Inductive Proofs / 1.4:
The Central Concepts of Automata Theory / 1.5:
Summary of Chapter 1 / 1.6:
Gradiance Problems for Chapter 1 / 1.7:
References for Chapter 1 / 1.8:
Finite Automata / Chapter 2:
An Informal Picture of Finite Automata / 2.1:
Deterministic Finite Automata / 2.2:
Nondeterministic Finite Automata / 2.3:
An Application_ Text Search / 2.4:
Finite Automata With EpsilonTransitions / 2.5:
Summary of Chapter 2 / 2.6:
Gradiance Problems for Chapter 2 / 2.7:
References for Chapter 2 / 2.8:
Regular Expressions and Languages / Chapter 3:
Regular Expressions / 3.1:
Finite Automata and Regular Expressions / 3.2:
Applications of Regular Expressions / 3.3:
Algebraic Laws for Regular Expressions / 3.4:
Summary of Chapter 3 / 3.5:
Gradiance Problems for Chapter 3 / 3.6:
References for Chapter 3 / 3.7:
Properties of Regular Languages / Chapter 4:
Proving Languages Not to Be Regular / 4.1:
Closure Properties of Regular Languages / 4.2:
Decision Properties of Regular Languages / 4.3:
Equivalence and Minimization of Automata / 4.4:
Summary of Chapter 4 / 4.5:
Gradiance Problems for Chapter 4 / 4.6:
References for Chapter 4 / 4.7:
Context-Free Grammars and Languages / Chapter 5:
Context-Free Grammars / 5.1:
Parse Trees / 5.2:
Applications of Context-Free Grammars / 5.3:
Ambiguity in Grammars and Languages / 5.4:
Summary of Chapter 5 / 5.5:
Gradiance Problems for Chapter 5 / 5.6:
References for Chapter 5 / 5.7:
Pushdown Automata / Chapter 6:
Definition of the Pushdown Automaton / 6.1:
The Languages of a PDA / 6.2:
Equivalence of PDA's and CFG's / 6.3:
Deterministic Pushdown Automata / 6.4:
Summary of Chapter 6 / 6.5:
Gradiance Problems for Chapter 6 / 6.6:
References for Chapter 6 / 6.7:
Properties of Context-Free Languages / Chapter 7:
Normal Forms for Context-Free Grammars / 7.1:
The Pumping Lemma for Context-Free Languages / 7.2:
Closure Properties of Context-Free Languages / 7.3:
Decision Properties of CFL's / 7.4:
Summary of Chapter 7 / 7.5:
Gradiance Problems for Chapter 7 / 7.6:
References for Chapter 7 / 7.7:
Introduction to Turing Machines / Chapter 8:
Problems That Computers Cannot Solve / 8.1:
The Turing Machine / 8.2:
Programming Techniques for Turing Machines / 8.3:
Extensions to the Basic Turing Machine / 8.4:
Restricted Turing Machines / 8.5:
Turing Machines and Computers / 8.6:
Summary of Chapter 8 / 8.7:
Gradiance Problems for Chapter 8 / 8.8:
References for Chapter 8 / 8.9:
Undecidability / Chapter 9:
A Language That Is Not Recursively Enumerable / 9.1:
An Undecidable Problem That Is RE / 9.2:
Undecidable Problems About Turing Machines / 9.3:
Post's Correspondence Problem / 9.4:
Other Undecidable Problems / 9.5:
Summary of Chapter 9 / 9.6:
Gradiance Problems for Chapter 9 / 9.7:
References for Chapter 9 / 9.8:
Intractable Problems / Chapter 10:
The Classes P and NP / 10.1:
An NP-Complete Problem / 10.2:
A Restricted Satisfiability Problem / 10.3:
Additional NP-Complete Problems / 10.4:
Summary of Chapter 10 / 10.5:
Gradiance Problems for Chapter 10 / 10.6:
References for Chapter 10 / 10.7:
Additional Classes of Problems / Chapter 11:
Complements of Languages in NP / 11.1:
Problems Solvable in Polynomial Space / 11.2:
A Problem That Is Complete for PS / 11.3:
Language Classes Based on Randomization / 11.4:
The Complexity of Primality Testing / 11.5:
Summary of Chapter 11 / 11.6:
Gradiance Problems for Chapter 11 / 11.7:
References for Chapter 11 / 11.8:
Index
Automata: The Methods and the Madness / Chapter 1:
Why Study Automata Theory / 1.1:
Introduction to Formal Proof / 1.2:
6.

図書

東工大
目次DB

図書
東工大
目次DB
J.E.ホップクロフト, J.D.ウルマン共著 ; 野崎昭弘, 木村泉訳者代表
出版情報: 東京 : サイエンス社, 1971.6  viii, 285p ; 22cm
シリーズ名: サイエンスライブラリ情報電算機 ; 6
所蔵情報: loading…
目次情報: 続きを見る
1 言語とその表現
   1.1 アルファベットと言語 1
   1.2 手続とアルゴリズム 3
   1.3 言語の表現 6
   演習問題 8
2 文法
   2.1 動機 9
   2.2 文法の形式的概念 11
   2.3 文法の型 15
   2.4 空文 17
   2.5 文脈依存文法の帰納性 19
   2.6 文脈自由文法における導出の木 22
   演習問題 28
3 有限オートマトンと正規文法
   3.1 有限オートマトン 30
   3.2 同値関係と有限オートマトン 32
   3.3 非決定性有限オートマトン 35
   3.4 有限オートマトンと3型文法 39
   3.5 3型文法の性質 42
   3.6 有限オートマトンについての決定可能な問題 47
   3.7 2方向有限オートマトン 49
   演習問題 54
4 文脈自由文法
   4.1 文脈自由文法の簡約化 56
   4.2 Chomsky標準形 61
   4.3 Greibach標準形 63
   4.4 有限性問題の決定可能性と"uvwxy定理" 69
   4.5 自己埋めこみ性 73
   4.6 文脈自由文法のε-規則 75
   4.7 特別な型の文脈自由言語と文脈自由文法 76
   演習問題 78
5 プッシュダウン・オートマトン
   5.1 pd-オートマトンとは 81
   5.2 pd-オートマトンの定義 83
   5.3 非決定性pd-オートマトンと文脈自由言語 88
   演習問題 93
6 Turing機械
   6.1 Turing機械 95
   6.2 Turing機械の定義と表示法 95
   6.3 Turing機械の構成技法 100
   6.4 手続としてのTuring機械 107
   6.5 Turing機械の諸変形 108
   6.6 基本型に等価な制限されたTuring機械 115
   演習問題 118
7 Turing機械:停止問題,O型言語
   7.1 概説 120
   7.2 万能Turing機械 120
   7.3 停止問題の決定不能性 126
   7.4 帰納的集合のクラス 128
   7.5 Turing機械とO型文法 129
   演習問題 133
8 線型有界オートマトンと文脈依存言語
   8.1 序論 134
   8.2 線型有界オートマトンと文脈依存言語の関係 135
   8.3 文脈依存言語は帰納的集合の部分クラスである 136
   演習問題 138
9 言語の演算
   9.1 序論 139
   9.2 基本演算のもとでの閉包性 139
   9.3 写像のもとでの閉包性 143
   演習問題 154
10 時間限定Turing機械およびテープ限定Turing機械
   10.1 序論 156
   10.2 諸定義 156
   10.3 「加速定理」および「テープ節約定理」 159
   10.4 テープ1本のTuring機械と通過列 167
   10.5 テープ計算量の下界 172
   10.6 テープ計算量および時間計算量の階層 176
   演習問題 182
11 文脈自由言語の認識に要する時間とテープ量の限界
   11.1 序論 185
   11.2 文脈自由言語の認識に要する時間 185
   11.3 文脈自由言語の認識に要するテープ量 190
   演習問題 194
12 決定性プッシュダウン・オートマトン
   12.1 序論 196
   12.2 決定性言語の補集合 197
   12.3 決定性言語の性質 202
   12.4 非決定性文脈自由言語 212
   12.5 LR(k)文法 212
   演習問題 221
13 スタックオートマトン
   13.1 定義 223
   13.2 スタックオートマトンの変型 227
   13.3 2方向スタックオートマトンの能力 228
   13.4 1方向スタックオートマトンの能力 239
   13.5 スタックオートマトンの帰納性 247
   13.6 閉包の性質 249
   演習問題 249
14 決定可能性
   14.1 決定可能な問題とそうでない問題 251
   14.2 Postの対応問題 252
   14.3 文脈依存言語に関する問題 260
   14.4 文脈自由言語の決定不能問題 260
   14.5 文脈自由言語の曖昧さ 263
   14.6 決定性文脈自由言語に関する決定不能問題 272
   14.7 正規,LR(k),文脈自由,文脈依存,O型の各文法に対する決定問題の結果の要約 273
   演習問題 274
文献 277
索引 283
1 言語とその表現
   1.1 アルファベットと言語 1
   1.2 手続とアルゴリズム 3
7.

図書

図書
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
出版情報: Reading, Mass. : Addison-Wesley, c1983  xi, 427 p. ; 25 cm
シリーズ名: Addison-Wesley series in computer science and information processing
所蔵情報: loading…
8.

図書

図書
Avrim Blum, John Hopcroft, Ravindran Kannan
出版情報: Cambridge : Cambridge University Press, 2020  viii, 424 p. ; 26 cm
所蔵情報: loading…
9.

図書

図書
J. ホップクロフト, R. モトワニ, J. ウルマン共著 ; 野崎昭弘 [ほか] 共訳
出版情報: 東京 : サイエンス社, 2003  2冊 ; 21cm
シリーズ名: Information & computing ; 3-4
所蔵情報: loading…
10.

図書

図書
A.V.エイホ, J.E.ホップクロフト, J.D.ウルマン著 ; 大野義夫訳
出版情報: 東京 : 培風館, 1987.3  x, 387p ; 22cm
シリーズ名: 情報処理シリーズ ; 11
所蔵情報: loading…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼