created: 01/06/01; revised: 03/28/01, 12/22/01, 09/08/06, 07/15/07
created: 01/06/01; revised: 03/28/01, 12/22/01, 09/08/06, 07/15/07
A finite state automaton is a conceptual machine that inputs a string of symbols and either rejects the string or accepts the string. Finite-state automata are often used to design or to explain actual machines. The actual machines can be hardware machines or software machines (programs). The properties of finite state automata are well known. If a problem can be described as a finite automaton, then the problem is well understood, and the solution is at hand.
A regular expression is a compact way of specifying a finite automaton. Regular expressions are especially useful for dealing with user input. Often, a program allows users to enter data in several ways and ignores minor errors. This is best done using regular expressions. Regular expressions and the Java classes that use them are explained in detail in later chapters.
Finite state automata are studied in several computer science courses: Foundations of Computer Science, Computer Architecture, Natural Language Processing, Systems Programming, Compiler Design, Operating Systems, Database Systems, Networking, and others. They also are studied outside of computer science in mathematics and linguistics.
The ideas behind finite state automata are the basis of several other abstract machines, such as push-down automata and Turing machines that are important in mathematics and computer science. They are also the basis of cellular automata, which are studied in computability theory, mathematics, physics, biology, and nanotechnology. (But none of these topics are discussed in these notes.)
Finite-state automata are used in embedded programming. The behavior of a physical device is often implemented as a finite automaton. Everytime you microwave a pizza or drive your car you are using a finite automaton.
In these chapters, string usually means "a sequence of characters". The characters are those available on typical computer keyboards.
Which of the following are strings:
abc abc abc GrandTotal <HREF>