Automata and formal languages

Notation

1. with ,
2. finite set of symbols
   We call the set of -strings of length .
   Set theoretic convention:
   ; write
3. Empty string
4. the set of -strings
5. If and , then is the unique initial segment of with length .
6. The set of nonempty strings
7. the concatenation of and
8. Write for when is string containing only
9. string of length containing only
10. If then there is a natural
11. Set is infinite if injects into it
12. 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

Register Machine