Introduction: Despite their simple appearance, DFAs are incredibly powerful and versatile! Here are some examples of their power:
Most questions about DFAs are algorithmically decidable. In particular, the following questions about DFAs are decidable:
Does a given DFA accept a given input?
Does a given DFA have an empty language?
Is the language of a given DFA all possible strings over Σ?
Are two given DFAs equivalent?
DFAs have many desirable properties, some of which are the following:
Limitations of DFAs
DFAs have two main limitations. First, despite being adequately expressive, they may require “too many” (an exponential number) states, which does adversely affect the space/time requirements of DFA-based algorithms. Second, for classifying strings based on many frequently occurring patterns, DFAs are simply inadequate. For instance, it is impossible to build a DFA that accepts all and only those strings containing an equal number of 0s and 1s. See Exercises 8.19, 8.20, and 8.21. We shall soon see that using the concept of non-determinism, we can obtain exponentially more succinct finite-state representations, giving rise to the next machine type we shall study, namely, nondeterministicfinite automata (NFA).
Considering Exercise 8.20, one can easily prove that there can exist no DFA. A proof sketch goes as follows:
It is obvious that to recognize a language such as L above, all we need to do is add a single stack to the DFA D. Doing so, we obtain a machine known as deterministic push-down automaton (DPDA). In general, by adding different kinds of data structures to the finite-state control, one can handle languages whose strings have more complicated structures. In Section 8.1.4, we shall now present a few examples that illustrate this point.