2.5 Finite Automata and Regular Expressions 53
(b) The set of all binary strings ending with 00 or 01 or 10.
(c) The set of binary strings that contain both 001 and 110 as sub-
strings or contain neither 001 nor 110 as a substring.
(d) The set of binary strings in which both the fourth symbol from
the right and the fourth from the left symbols are 0. [Note: Both
strings 0110 and 10101 belong to this set.]
* 3. Consider the following multiplication table on {a, b, c}:Construct NFA’s for the following languages:
(a) {J: 1 value(z) # value(@)}.
(b) {zy 1 value(z) = value(#)}.
(c) {zy 1 value(z) = value(y)}.2.5 Finite Automata and Regular Expressions
In this section, we are going to show that DFA’s accept exactly the class of
regular languages. This result is to be established in three steps:
(1) If L is a regular language, then it is accepted by an NFA.
(2) If L is accepted by an NFA, then it is accepted by a DFA.
(3) If L is accepted by a DFA, then it is a regular language.
In Section 1.3, we showed that a regular expression r has a labeled digraph
representation G(r) such that for each string X, x E L(r) if and only if there
is a path in G(r) from the initial vertex to the final vertex whose associated
labels are exactly the string 2. Furthermore, each edge of G(r) is labeled by
exactly one symbol from {E} U C. Thus, it is clear that G(r) is the transition
diagram of an NFA, with the initial vertex denoting the initial state and the
final vertex denoting the unique final state. That is, part (1) above has been
proven in Section 1.3.
Next, we note that part (2) h as already been done in Section 2.4. Therefore,
by combining parts (1) and (2)) we can construct a DFA from any given regular
expression. Before we prove part (3)) let us see some examples of constructing
an NFA or a DFA from a given regular expression.
Example 2.29 Find a DFA accepting the language 10 + (0 + ll)O*l.
So&ion. First, we find an NFA to accept this language by using the method
of Section 1.3. Then we transform this NFA to a DFA. The result is shown
in Figure 2.34. cl