Constructing Smaller DFAs using Partial Languages

Partial words are sequences over an alphabet in which certain positions are undefined. We represent these undefined positions with a “hole” symbol ◊. If we restrict what this hole symbol can represent, we can use partial words to compress the representation of regular languages. Doing so allows the creation of DFAs smaller than that recognizing the original language which recognize the compressed language. However, the new DFA is larger than the minimal NFA recognizing the original language. We investigate how these assorted sizes are related.

Keywords: Combinatorics on words; Partial words; Regular languages; DFAs; NFAs.