State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages

摘要

The GF(2)-inverse operation on formal languages is known to have state complexity 2~n + 1 for alphabets with at least three symbols, and 2~(n-1) + 1 for a one-symbol alphabet. In this paper, it is shown that, for a two-symbol alphabet, its state complexity is exactly 3/4 2~n + 3. For a more general operation of GF(2)-star, its state complexity for a binary alphabet remains 2~n + 1.