[Overview] [Previous] [Next]

Vocabulary

accept
acceptor
alphabet
ambiguous
automaton
basis
binary Turing machine
blank
bootstrapping
cardinality
child
Chomsky hierarchy
Chomsky Normal Form
closed (under an operation)
complement of a set
complexity theory
composition
concatenation
configuration
context free grammar
context-free language
context-sensitive grammar
context-sensitive language
dead code problem
denumerable
derivation step
derivation tree
deterministic context-free language
deterministic finite acceptor
deterministic pushdown automaton
diagonalization
directly derives
directly recursive
disjoint
domain
edges
effective procedure
elements
empty set
empty string
enumerate
equivalent
error state
exhaustive search parsing
extended transition function
final state
function
Gödel numbers
general recursive function
generalized transition graph
grammar
graph
Greibach Normal Form
halting problem
height
homomorphic image
homomorphism
indirectly recursive
inductive assumption
inherently ambiguous
initial state
input alphabet
instantaneous description
intersection
intractable problem
language
leaf
left-linear grammar
left-recursive
leftmost derivation
length of a string
level of a vertex
linear language
linear-bounded automaton
membership criterion
monus
move
mu-recursive
multidimensional Turing machine
multitape Turing machine
n-track Turing machine
noncontracting grammar
nondeterministic
nondeterministic finite acceptor
nondeterministic polynonomial time
nondeterministic pushdown automaton
nondeterministic Turing machine
nonterminal
NP-complete problems
off-line Turing machine
one-to-one correspondence
oracle
order statistic
parent
parsing
partial derivation tree
partial function
path
pigeonhole principle
polynomial-time algorithm
positive closure
Post's correspondence problem
powerset
prefix
primitive recursive function
primitive regular expression
production
projector functions
proof by contradiction
proper subset
pumped string
pumping lemma
quantum computer
random-access machine
range
read-write head
recursive
recursive function theory
recursive language
recursively enumerable language
reduce (one problem to another)
reductio ad absurdum
regular expression
regular grammar
regular language
reject
reverse of a string
right quotient
right-linear grammar
rightmost derivation
root
rule
semi-infinite tape
sentence
sentential form
set
set difference
simple path
space complexity
squares
stack alphabet
stack start symbol
standard representation
star closure
start state
start symbol
state
state set
state transitions
stay option
string
subset
successor function
suffix
tape
tape alphabet
tape head
terminal symbol
time complexity
tractable problem
transducer
transition function
trap state
tree
Turing computable
Turing machine
union
universal set
universal Turing machine
unrestricted grammar
variable
vertex (vertices)
walk
word
yield of the tree
zero function


Copyright © 1996 by David Matuszek
Last modified Apr 24, 1996