go to previous page   go to home page   go to next page
abc abc


All of these examples are strings. The space character in abc abc is a legitimate chracter and is part of the string.

Where it is needed for clarity, an square character will be used to represent a space. For example, the above string might be shown as: abc□abc.


In these chapters, string  means a sequence of characters. Of course, the order of the characters is important. The string ABCD is not the same string as DBAC.

Automata are not limited to processing text. A the string an automaton processes could be a sequence of mouse clicks, a sequence of states of a processor chip, a sequence of voltage levels on a wire, or a sequence of pixels in a digital image. An automaton might model interaction of a user with GUI. The correct sequence of button clicks and other control actions could be guided by the automaton. Or, an automaton could model the interaction of a user with an on-line vendor. Automata are used in many problem domains.

So, although most of these pages show an automaton processing strings of characters, that is just a convenient example.


A particular computer game has a hero progressing through a mysterious cave, chamber by chamber. In each chamber there is a different set of challenges.

What abstract machine could be used to model this game?