Automata and Formal Languages: Examples
Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
Universality
The example shows an NFA, for which
we want to check universality. We show the determinized NFA
and illustrate how not all states need to be explored. For instance,
if one takes the 1-a->2 transition first, the 1-b->3 edge of the DFA can
be redirected to 2, because {2} is a subset of {2,3}. The same holds
for the a-edge between {3,4} and {1,3,4}. In the end, one only needs to
construct three states to show universality -- rather than 8 as is the
case for the full DFA.