Index



A
(language) AcceptsEverything
(language) Accepts(Lambda)
(language) AcceptsNothing
accepting state (of FA)
alphabet

C
Chomsky formal languages
Chomsky hierarchy
class NP
(set) closed under operation
complement of DFA and regular language
concatenation of strings
concatenation of languages
configuration of PDA
configuration of Turing machine
context-free grammar
context-sensitive grammar
context-free language
conversion of NFA to DFA
conversion of NFA- to NFA

D
dead state of FA
decision problem
* of DFA
DFA (deterministic finite automaton)

E
empty/null string
equality of regular expressions

F
finite language
function computed by Turing machine

G
grammar

H
halting of Turing machine
halting problem
Hasse diagram

I
indistinguishable strings
initial state (of FA)
intersection of DFAs and regular languages
intractable problem

K
Kleene star
Kleene's Theorem -- Part 1
Kleene's Theorem -- Part 2

L
language
language accepted by DFA
language accepted by NFA
language accepted by NFA- language accepted/decided by Turing machine

length of string/word

M
minimal element
minimization of DFA

N
next state function of DFA
next state function of NFA
NFA (nondeterministic finite automaton)
NFA- (nondeterministic finite automaton with transitions)
nondeterministic Turing machine
(language) NonSelfAccepting
NP-complete problem
NP-hard problem

O
out-degree

P
phrase structure grammar
polynomial-time reducible
power of symbol, string, language

prefix
Presburger arithmetic
push-down automaton (PDA)


Q
quantifiers -- see universal and existential quantifiers
quasi order

R
reactive system
regular expression
regular grammar
regular language
REV (reversal of string)

S
simulation of computer by Turing machine
state (of FA)
(state) transition diagram
string
string accepted by DFA
string accepted by NFA
string accepted by NFA- string accepted/decided by Turing machine
substring
suffix
syntax of proposition


T
transition function of DFA
transition function of NFA
transition function of NFA-
transition table
Turing machine

U
unsatisfiable wff

V
vertex

W
wff





Table of Contents, and Contents
Back to CS 390 Home Page
Sample Study Schedule
Back to CS390 TechEd Information Page