Notation
with , finite set of symbols We call the set of -strings of length . Set theoretic convention: ; write - Empty string
the set of -strings - If
and , then is the unique initial segment of with length . The set of nonempty strings the concatenation of and - Write
for when is string containing only string of length containing only - If
then there is a natural - Set is infinite if
injects into it - Set is countable if its empty or
surjects onto it
Rewrite System Formal Language Grammar
The Chomsky Hierarchy Regular Formal Language Context-Free Formal Language