proper subset
pumping lemma
for context-free languages for linear languages for regular languages
pushdown automata deterministic
nondeterministic R
read-write head recursive functions recursive languages recursively enumerable
languages, reduction
of number of states in a dfa of undecidable problems polynomial-time regular
expressions regular grammars regular languages relations
reverse
of a language
of string
rewriting systems Rice's theorem
right-linear grammar rightmost derivation right quotient of a language root of a
tree
S
satisfiablity problem 3SAT
semantics of a programming language sentence
sentential form sets
countable
size
uncountable
set operations
s-grammar
simulation
stack
alphabet
start symbol
standard representation of a regular language state-entry problem storage of an
automaton string
empty
length