Seja A um autômato finito não determinístico que reconhece ...

o número de estados de A não pode ser maior do que o número de estados de B.

se A tem o menor número de estados dentre todos os autômatos finitos não determinísticos que reconhecem L, e se B tem o menor número de estados dentre todos os autômatos finitos determinísticos que reconhecem L, então ambos têm o mesmo número de estados.

se A tem o menor número de estados dentre todos os autômatos finitos não determinísticos que reconhecem L, e se B tem o menor número de estados dentre todos os autômatos finitos determinísticos que reconhecem L, o número de estados de A e B não pode ser igual.

se A tem o menor número de estados dentre todos os autômatos finitos não determinísticos que reconhecem L, e se B tem o menor número de estados dentre todos os autômatos finitos determinísticos que reconhecem L, o número de estados de B é no máximo o dobro do número de estados de A.

se A tem o menor número de estados dentre todos os autômatos finitos não determinísticos que reconhecem L, e se B tem o menor número de estados dentre todos os autômatos finitos determinísticos que reconhecem L, o número de estados de B pode ser exponencial no número de estados de A.