Fundamental Concepts

There are three fundamental concepts that we will be working with in this course:

Languages
- A language is a subset of the set of all possible strings formed from a given set of symbols.
- There must be a membership criterion for determining whether a particular string in in the set.
Grammars
- A grammar is a formal system for accepting or rejecting strings.
- A grammar may be used as the membership criterion for a language.
Automata
- An automaton is a simplified, formalized model of a computer.
- An automaton may be used to compute the membership function for a language.
- Automata can also compute other kinds of things.