A language is a potentially infinite set of strings. A language can be described in a variety of ways:
- Enumerate the set
- Regular expression
- Set comprehension
- Grammar Languages are classified by the complexity of the machine needed to recognize them
- Regular (FA)
- LL(1) (Deterministic push-down automaton)
- Context Free Grammar (Non-deterministic push-down automaton)
Note
Deterministic = fixed choices
Push-down = stack → recursion