Module Overview & Automata Types
The main points of study in this module are:
- Finite Automata:
- Related to regex.
- Grammars:
- Extracting the meaning from a program.
- Turing Machines:
- The general model of computing.
Some Kinds of Machines
| Type | Description |
|---|---|
| Finite Automata | Devices with a small amount of memory. Used to model very simple things. |
| Push-down Automata | Devices with infinite memory that can be accessed in a very limited way. Used to parse grammars. |
| Turing Machines | Devices with infinite memory. These are at lease as powerful as computers. |
| Resource-bounded Turing Machines | Infinite memory, but bounded by running time/memory. These are computers that run reasonably fast/efficiently. |