Index
Absorp tion 3, 44, 53
Absur dity 255, 259, 302
Accep tor 59, 99, 114, 170, 186, 188
Ackermann’s func tion 229, 231, 234
Alpha bet 18, 43, 55
Ambi gu ity 127, 129-130
Ambig u ous gram mar 130, 149, 155
Asso cia tiv ity 2, 44, 52-53, 259
Autom a ton 58, 97, 99, 108
Axiom 245, 299
Biconditional 249, 293, 301
Bijection 13, 43, 54
Binary turing machine 196, 208
Blank 187, 207
Boolean logic 27, 43, 56
Boolean satisfiability 238, 243
Bottomup pars ing 128-129, 149, 155
Bub ble sort 236, 243
Car di nal ity 7, 43-44, 46, 53, vii
Car te sian prod uct 7, 53, vii
Chomsky nor mal form (CNF) 142, 149,
157, 167, 184
Cir cuit 16, 55
Clo sure 91, 96, 112, 175
Commutativity 2, 44, 52, 259
Com ple ment 2, 43, 52, vii
Com plex ity the ory 235, 240, 242
Com po si tion of func tions 222, 231, 233
Con cat e na tion 18, 56, 80-81, 92, 99
Con junc tion 27, 43, 56, 247, 290, 292,
300
Con nected graph 16, 55
Con text sen si tive gram mar 210, 214, 216
Con text sen si tive lan guage 210-211, 214,
216-217
Con text-free gram mar (CFG) 115,
148-149, 153, 167
Con tin gency 255, 257, 293, 301
Con tra dic tion 94, 173, 203, 255-256, 293,
301
Contrapositive 259-260, 302
Cycle 17, 55, 94
Deci sion algo rithm 176, 180, 185
Degree of ver tex 15, 43, 55
DeMorgan’s law 3, 6, 44, 53, 259, 290
Der i va tion tree 118, 125, 154
Deter min is tic autom ata 58, 109
Directed graph 17, 43, 55
Dis joint set 7, 44, 53
Disjunction 27, 43, 56, 248, 290, 292,
300
Dis junc tive syl lo gism 259, 293, 302
Distributivity 3, 44, 52, 259, 273
Empty pro duc tion removal 133, 184
Empty set 1, 43, vii
Empty string 18, 56, vii
Equiv a lence 259, 266, 302
Equiv a lence rela tion 9-11, 44, 53, 97-98
Exhaus tive search pars ing 128, 155
Expor ta tion 259, 302
Finite accep tor 110, 170
For mal sys tem 197, 218, 230, 232, 234
completeness 218, 230, 232
consistency 218, 230, 232
Func tion 12, 43, 54
Godel’s proof of num bers 218, 233
Gram mar 37-38, 57, 117, viii
Graph 15, 55
Absorp tion 3, 44, 53
Absur dity 255, 259, 302
Accep tor 59, 99, 114, 170, 186, 188
Ackermann’s func tion 229, 231, 234
Alpha bet 18, 43, 55
Ambi gu ity 127, 129-130
Ambig u ous gram mar 130, 149, 155
Asso cia tiv ity 2, 44, 52-53, 259
Autom a ton 58, 97, 99, 108
Axiom 245, 299
Biconditional 249, 293, 301
Bijection 13, 43, 54
Binary turing machine 196, 208
Blank 187, 207
Boolean logic 27, 43, 56
Boolean satisfiability 238, 243
Bottomup pars ing 128-129, 149, 155
Bub ble sort 236, 243
Car di nal ity 7, 43-44, 46, 53, vii
Car te sian prod uct 7, 53, vii
Chomsky nor mal form (CNF) 142, 149,
157, 167, 184
Cir cuit 16, 55
Clo sure 91, 96, 112, 175
Commutativity 2, 44, 52, 259
Com ple ment 2, 43, 52, vii
Com plex ity the ory 235, 240, 242
Com po si tion of func tions 222, 231, 233
Con cat e na tion 18, 56, 80-81, 92, 99
Con junc tion 27, 43, 56, 247, 290, 292,
300
Con nected graph 16, 55
Con text sen si tive gram mar 210, 214, 216
Con text sen si tive lan guage 210-211, 214,
216-217
Con text-free gram mar (CFG) 115,
148-149, 153, 167
Con tin gency 255, 257, 293, 301
Con tra dic tion 94, 173, 203, 255-256, 293,
301
Contrapositive 259-260, 302
Cycle 17, 55, 94
Deci sion algo rithm 176, 180, 185
Degree of ver tex 15, 43, 55
DeMorgan’s law 3, 6, 44, 53, 259, 290
Der i va tion tree 118, 125, 154
Deter min is tic autom ata 58, 109
Directed graph 17, 43, 55
Dis joint set 7, 44, 53
Disjunction 27, 43, 56, 248, 290, 292,
300
Dis junc tive syl lo gism 259, 293, 302
Distributivity 3, 44, 52, 259, 273
Empty pro duc tion removal 133, 184
Empty set 1, 43, vii
Empty string 18, 56, vii
Equiv a lence 259, 266, 302
Equiv a lence rela tion 9-11, 44, 53, 97-98
Exhaus tive search pars ing 128, 155
Expor ta tion 259, 302
Finite accep tor 110, 170
For mal sys tem 197, 218, 230, 232, 234
completeness 218, 230, 232
consistency 218, 230, 232
Func tion 12, 43, 54
Godel’s proof of num bers 218, 233
Gram mar 37-38, 57, 117, viii
Graph 15, 55