Equivalence of Automata

Two automata A and B are said to be equivalent if both accept exactly the same set of input strings. Formally, if two automata A and B are equivalent then

• if there is a path from the start state of A to a final state of A labeled a1a2..ak, there there is a path from the start state of B to a final state of B labeled a1a2..ak.
• if there is a path from the start state of B to a final state of B labeled b1b2..bj, there there is a path from the start state of A to a final state of A labeled b1b2..bj.

[the_ad id=”112″]

Equivalence of Deterministic and Nondeterministic Automata

To show that there is a corresponding DFA for every NDFA, we will show how to remove nondeterminism from an NDFA, and thereby produce a DFA that accepts the same strings as the NDFA.

The basic technique is referred to as subset construction, because each state in the DFA corresponds to some subset of states of the NDFA.

The idea is this: as we trace the set of possible paths thru an NDFA, we must record all possible states that we could be in as a result of the input seen so far. We create a DFA which encodes the set of states of the NDFA that we could be in within a single state of the DFA.

Subset Construction for NDFA

To create a DFA that accepts the same strings as this NDFA, we create a state to represent all the combinations of states that the NDFA can enter.

From the previous example (of an NDFA to recognize input strings containing the word “main”) of a 5 state NDFA, we can create a corresponding DFA (with up to 2^5 states) whose states correspond to all possible combinations of states in the NDFA:

  {},
  {s0}, {s1}, {s2}, {s3}, {s4},
  {s0, s1}, {s0, s2}, {s0, s3}, {s0, s4},
  {s1, s2}, {s1, s3}, {s1, s4},
  {s2, s3}, {s2, s4},
  {s3, s4},
  {s0, s1, s2}, {s0, s1, s3}, {s0, s1, s4},
  {s0, s2, s3}, {s0, s2, s4},
  {s0, s3, s4},
  {s1, s2, s3}, {s1, s2, s4},
  {s1, s3, s4},
  {s2, s3, s4},
  {s0, s1, s2, s3}, {s0, s1, s2, s4},
  {s0, s1, s3, s4}, {s0, s2, s3, s4},
  {s1, s2, s3, s4},
  {s0, s1, s2, s3, s4}

Note that many of these states won’t be needed in our DFA because there is no way to enter that combination of states in the NDFA. However, in some cases, we might need all of these states in the DFA to capture all possible combinations of states in the NDFA.

Subset Construction for NDFA (cont)

A DFA accepting the same strings as our example NDFA has the following transitions:

  {s0} -m-> {s0,s1}
  {s0} -not m-> {s0}
  
  {s0,s1} -m-> {s0,s1}
  {s0,s1} -a-> {s0,s2}
  {s0,s1} -not m,a-> {s0}
  
  {s0,s2} -m-> {s0,s1}
  {s0,s2} -i-> {s0,s3}
  {s0,s2} -not m,i-> {s0}
  
  {s0,s3} -m-> {s0,s1}
  {s0,s3} -n-> {s0,s4}
  {s0,s3} -not m,n-> {s0}

The start state is {s0} and the final state is {s0,s4}, the only one containing a final state of the NDFA.

Limitations of Finite Automata

The defining characteristic of FA is that they have only a finite number of states. Hence, a finite automata can only “count” (that is, maintain a counter, where different states correspond to different values of the counter) a finite number of input scenarios.

There is no finite automaton that recognizes these strings:

• The set of binary strings consisting of an equal number of 1’s and 0’s
• The set of strings over ‘(‘ and ‘)’ that have “balanced” parentheses

The ‘pumping lemma’ can be used to prove that no such FA exists for these examples.