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.