The Power Of Dfas

Introduction: Despite their simple appearance, DFAs are incredibly powerful and versatile! Here are some examples of their power:

• The most touted applications of DFAs are in the area of compiler scanner generation, where a scanner is a program that recognizes the patterns hidden within strings representing keywords, floating-point numbers, etc.

• Exercises 8.16 and 8.17 demonstrate that using DFAs, one can perform division either going MSB-first (the ‘high-school’ method) or even LSB-first. Only a finite amount of information needs to be remembered across digits (essentially, the remainder after division; fully explained in these exercises).

• DFAs can be used to compactly represent Boolean functions (Chapter 11) or even help determine the validity of formulas in certain branches of mathematical logic, known as Presburger arithmetic(Chapter 20).

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:

• Given any DFA d, one can algorithmically obtain another DFA d’whose language is the reverse of the language of d.
• Given any DFA d, one can algorithmically obtain another DFA d’whose language is the complement of the language of d.

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:

• Suppose there exists an M-state DFA for this language. Consider the string w = (M )M.
• w causes M 1 states to be visited even while processing (M, a string of M left parentheses.
• Since only M of these states can be distinct states, one state repeats during the (M traversal.
• Therefore, there also exists a shorter, non state-repeating path leading to the same final state. However, taking this path causes the DFA to omit one or more (, thus causing it to accept (k)M for some k <M – a contradiction with the fact that this is the DFA for the language L.

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.