ind6

A-derivable variable
DPDA
empty stack
FA
language
language acceptor
language of palindromes
NFA
PDA
TM
Accepting configuration
Add
Agrawal
Algebraic-expression grammar
Algorithm
Algorithm procedure
Alphabet
Ambiguity
AnBn
Ancestor
Answers to selected exercises
Arithmetic progression
Associative law for unions
Associative laws
counter
LBA
two-stack
Balanced
acceptance by DPDA
balanced string of parentheses
defined
language
recursive definition
smallest language
top-down parser
Balanced strings of parentheses
Bar-Hillel
Basis statement
Beigel
Bibliography
Biconditional
Big-Oh notation
Bijection
Binary operation
Boolean array
Bottom-up parser (SimpleExpr)
Bottom-up PDA
Bounded existential quantification
Bounded minimization
Bounded products
Bounded quantifications
Bounded sums
Bounded universal quantification
Bovet
Brown
Building computer with equivalence classes
Busy-beaver function
By final state
Canonical order
Cartesian product
CFG
CFG corresponding to a regular expression
CFGGenerateAll
CFGNonemptyIntersection
Characteristic function
Chomsky
Chomsky hierarchy
Chomsky normal form
Church
Church-Turing thesis
Church’s thesis
Closed under the operation
CNF
CNF-Tautology
Cobham
Codomain
Combining Turing machines
Commutative laws
Comparing two strings
CFL
definition
notation
Complementary problem
Complete subgraph
Complete subgraph problem
Composite natural numbers
Composites and primes
Composition
Compound propositions
Compound statement
Computable functions
G ̈odel numbering
minimization
μ-recursion
μ-recursive function
other approaches to computability
primitive recursive functions
quantification
Computation
Computation tree
Computational complexity
Cook-Levin theorem
NP-complete problems
NP-completeness
polynomial-time reductions
polynomial verifiability
set NP
set P 
time complexity of TM
Computational Complexity (Papadimitriou)
Concatenation
Conditional
Configuration number
Conjunction
Conjunctive normal form (CNF)
Connectives
Constant function
Context-free grammar (CFG)
Context-free language (CFL)
complement
context-free grammar
decision problems
derivation trees and ambiguity
grammar rules
intersection
pumping lemma
regular language/regular grammar
simplified forms/normal forms
undecidable problems
Context-sensitive grammar (CSG)
Context-sensitive language (CSL)
Contradiction
Contrapositive
Converse
Converting an NFA with -transitions to an FA
Converting CFG to Chomsky normal form
Cook
Cook-Levin theorem
Copying a string
Corescenzi
Correspondence systems
Countable set
Countable union of countable sets
Countably infinite set
Counter automaton
Counting the elements
Course-of-values recursion
CSG
CSL
CSLIsEmpty
δ ∗ 
Dangling else
Davis
DCFL
De Morgan laws
Decidable problems
Deciding a language
Decision problems
CFL
complementary problem
decidability
general form
languages accepted by FAs
reducing one to another
TM
yes-instances/no-instances
acceptance by empty stack
acceptance by FA
acceptance by PDA
acceptance by TM
accepting a language
ambiguity
Big-Oh notation
bounded minimization
bounded quantifications
Chomsky normal form
composition
context-free grammar
countable set
countably infinite set
CSG
CSL
decidable problems
DPDA
encoding function
equivalence class containing x
equivalence relation
extended transition function (δ ∗ )
extended transition function for NFA
finite automaton
G ̈odel number of sequence of natural numbers
initial function
−closure of set of states
L-indistinguishability relation
language generated by CFG
language property of TM
LBA
LMD
mate of left parentheses in balanced string
μ-recursive function
NB(G)
NFA
NP-complete language
NP-hard language
NSA
NT(G)
one-to-one function
onto function
PCP
PDA
polynomial-time reduction
primitive recursion
primitive recursive function
recursive
recursive definition of set of nullable variables
reducing one decision problem to another
reducing one language to another
regular grammar
regular languages over alphabet 
relation
RMD
S M 
SA
set A of same size as B or larger than B
set NP
set P 
strings distinguishable with respect to L
time complexity of NTM
time complexity of TM
TM computing a function
TM enumerating a language
Turing machine
unbounded minimization
universal TM
unrestricted grammar
valid computations of TM
verifier for language
Deleting a symbol
LMD
primitive recursive
RMD
strings
Derivation tree
Deterministic context-free language (DCFL)
Deterministic PDA (DPDA)
Diagonal argument
Difference
Direct proof
Disjoint set
Disjunction negation
Distributive laws
Div
DNF-Sat
Domain
Double-duty (L)
Doubly infinite tape
Dowling
DPDA
E 
Earley
egrep
Eliminating -transitions from an NFA
else
Empty set
Empty stack
Encoding function
End-marker
Enumerating a language
Equality relation
Equivalence class containing x
Equivalence classes of I L 
Equivalence relation
Erasing the tape
Eventually linear
Eventually periodic function
Exact cover problem
Exercises
Existential quantifier
Exponential notation
Expr
Expression graph
Extended transition function (δ ∗ )
sets defined recursively
successor
transition
Functions and equivalence relations
Factorial function
Fermat’s last theorem
FA
Finite automaton (FA)
acceptance/rejection
accepting {aa
accepting strings containing ab or bba
end
building computer with equivalence classes
converting NFA to
decision problems
defined
difference of two languages
distinguishing one string from another
language acceptor
lexical analysis
minimization algorithm
model of computation
NFA
pumping lemma
regular expression
string search algorithm
union
Finite set
Finite-state machine
First De Morgan law
Floyd
for statement
busy-beaver
characteristic
constant
defined
encoding
eventually periodic
factorial
initial
μ-recursive
one-to-one
onto
primitive recursive
projection
relabeling
relationships
Garey
Generalized regular expression
G ̈odel numbering
Goldbach’s conjecture
algebraic-expression
CFG
Chomsky hierarchy
converting CGF to Chomsky normal form
CSG
left-regular
linear
LL(1)
LL(k)
regular
right-regular
type 0
unrestricted
weak precedence
Grammar rules
grep
Halting problem
Halts
Hartmanis
Homomorphism
Hopcroft
Human computer
Identifier (C programming language)
if statement
Ignore the states
Immerman
Incompleteness theorem
Independent set of vertices
Indirect proof
Induction hypothesis
Induction step
Infinite set
InitConfig (n) 
Initial function
Inserting/deleting a symbol
Intersection
IsAccepting T 
IsAmbiguous
Isomorphic to M 2 
Isomorphism from M 1 to M 2 
Johnson
k-colorability problem
k-coloring
Karp
Kayal
Kleene
Kleene closure
Kleene star
Part I
Part II
Knuth
L-distinguishable
−closure of set of states
(S )
−transition
Language
accepting
CFG
Chomsky hierarchy
concatenation
countable set
CSL
DCFL
deciding
enumerating
grammar rules
large alphabets
NP-complete
NP-hard
NSA
over
programming language
pumping lemma/accepted by FA
recursive
reducing one to another
regular
SA
verifier
Language acceptor
Language over 
Language property
LBA
Left recursion
Left-regular grammar
Leftmost derivation (LMD)
Legal C programs
Levin
Levine
Lewis
Lewis
lex
Lexical analysis
Lexical analyzer
Lexical-analyzer generator
Lexicographic order
Linear-bounded automaton (LBA)
Linear grammar
Live variable
LL(1) grammar
LL(k) grammar
LMD
Logic and proofs
Logical connectives
Logical identities
Logical implication
Logical quantifier
Logically equivalent
Many-one reduction
Mason
Match
Mate
Mathematical induction
Mathematical tools and techniques
functions and equivalence relations
logic and proofs
recursive definition
structural induction
McCulloch
Membership problem
Membership table
Meta-statement
Minimization
Minimization algorithm
Mod
Mod 2
Modified correspondence systems
Modified Post correspondence problem (MPCP)
Modus ponens
Monus operation
Moore
Motwani
Move T 
MPCP
μ-recursion
μ-recursive function
Mult
Multitape Turing machines
Myhill
n-place predicate
Natural number
NB(G)
Nerode
NewPosn
NewState
NewSymbol
NewTapeNumber
Next blank
NFA
accepting languages
converting
corresponding to ((aa + b)*(aba)*bab)*
eliminating nondeterminism
formal definition
model of computation
No-instance
Non-context-free language
Non-self-accepting
eliminating
NB(G)
NT(G)
NTM
Nondeterministic bottom-up PDA [NB(G)]
Nondeterministic polynomial algorithms
Nondeterministic polynomial time
Nondeterministic top-down PDA [NT(G)]
Nondeterministic Turing machine (NTM)
Nonempty subset
NonemptyIntersection
NonPal
Nonpalindrome
Nonterminal
Nontrivial language property
Normal forms
NP-complete language
NP-complete problems
NP-completeness
NP-hard language
NSA
NT(G)
nth prime number
NTM
Null string
Nullable variables
Numeric literal
Oettinger
Ogden
Ogden’s lemma
One-to-one function
Onto function
Operation on a set
Ordered k-tuples
Ordered pairs
Pairwise disjoint
Pairwise L-distinguishable
Pal
Palindrome
Papadimitriou
Parenthesization
Parser
Parsing
Partial match
Partition
Partition problem
PCP
PerfectSquare
Perles
Pitts
Polynomial time
Polynomial-time reductions
Polynomial-time solution
Polynomial-time verifier
Post
Post machine
Post’s correspondence problem (PCP)
Power set
Precedence grammar
Pred
Prefix
Preserved under bijection
Previous blank
Prime
Prime
Primitive recursion
Primitive recursive derivation
Primitive recursive functions
Production
Program configuration
Programming-language syntax
Projection function
direct
indirect
logic
typical step
Proof by cases
Proof by contradiction
Proof by contrapositive
Proposition
Pumping lemma
{x ∈ {a
AnBnCn
context-free languages
defined
not accepted by FA
regular languages
theorem
XX
Pushdown automaton (PDA)
acceptance
bottom-up PDA
from CFG
CFG from given PDA
definitions/examples
deterministic PDA
formal definition
parsing
top-down PDA
Pythagorean school
Quantification
Quantified statements
Quantifier
Quotient and remainder Mod 2
Rabin
Reachable variable
Really identical
Recursive definition
Recursive definition of S M 
Recursive language
Recursively enumerable language
alternative name
Chomsky hierarchy
CSG/CSL
enumerating a language
more general grammars
recursive language
theorem
unrestricted grammar
which languages are recursively enumerable
Reducing one decision problem to another
Reducing one language to another
Reduction
Reductions and the halting problem
References (bibliography)
Regular expression
Regular grammar
Regular language
Relabeling function
Relation
Relation of congruence mod n on N
Relation on A containing all ordered pairs
Result T 
Reverse of a string
Rice’s theorem
Right-invariant
Right-regular grammar
Rightmost derivation (RMD)
RMD
Rosenkrantz
S M 
SA
Salomaa
Satisfiability problem
Satisfiable
Saxena
Schr ̈oder-Bernstein theorem
Sch ̈utzenberger
Selected bibliography
Selected exercises
Self-accepting
Self-embedded variable
Set
countable
countably infinite
disjoint
empty
finite
infinite
natural numbers
nonempty
NP
operation on
P 
power
subset
Set identities
Set of composite natural numbers
Set of legal C programs
Shamir
Shift move
Sigal
SimplePal
Simplified algebraic expressions
Simplified norms
Sipser
Solutions to selected exercises
Stack
Stack-emptying state
Star height
Start variable
State
Statement-sequence
Stearns
String
String over 
String search algorithm
Strong induction
Stronger statement
Structural induction
Sub
Subset
Subset construction
Subset construction to eliminate nondeterminism
Substring
Successor function
Suffix
Sum-of-subsets problem
Syntax diagram
Syntax of programming languages
Szelepcs ́eny
Tape head
Tautology
Terminal
Terminal symbol
3-Sat
TM configuration
Token
Top-down parser (Balanced)
Top-down PDA
Tractable problem
Transition function
copying a string
DPDA accepting AEzB
DPDA accepting Balanced
NFA with seven states
NT(G)
NT(G 1 )
PDA accepting AnBn
PDA accepting Pal
PDA accepting SimplePal
Transitive closure
Traveling salesman problem
Triple
Truth value
Turing
Turing-acceptable language
Turing-decidable language
Turing machine
Church-Turing thesis
combining
computing a function
configuration
countable set
current tape number
decision problems
defined
deleting a symbol
doubly infinite tape
enumerating a language
finite alphabet/finite set of states
halt states
language acceptor
language property
modified correspondence system
multitape
NTM
partial functions
Post machine
simpler machines
time complexity
two-stack automaton
universal
valid computations
Turing’s thesis
Two-stack automaton
2-tape TM
Type 0 grammar
U − A
Ullman
Unary operation
Unbounded minimization
Undecidable decision problems
CFL
PCP
reductions and the halting problem
SA/NSA
TM
Undecidable problem
Union
Universal quantifier
Universal Turing machine
Unix
Unrestricted grammar
Useful variable
Useless
Variable-occurrence
Verifier for language
Vertex cover
Vertex cover problem
Virus tester
Valid computations of TM
van
A-derivable
elements of V 
live
nullable
reachable
self-embedded
start
useful
useless
Weak precedence grammar
Weyuker
Within parentheses
yacc
Yes-instance
Younger
0–1 knapsack problem