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