[Syllabus] [Previous lecture]
There are three fundamental concepts that we will be working with in this
- 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.
- A grammar is a formal system for accepting or rejecting strings.
- A grammar may be used as the membership criterion for a language.
- An automaton is a simplified, formalized model of a computer.
- An automaton may be used to compute the membership function for a
- Automata can also compute other kinds of things.
Copyright © 1996 by David Matuszek
Last modified Jan 31, 1996