We explore small balanced vertex separators in NFA to regular expression conversion. We show that any class of finite automata whose underlying class of graphs admits “strongly sublinear separators” also admits shorter regular expressions. We propose a new state elimination ordering heuristic, called the “gate score” heuristic, which is a variant of the weight heuristic of Delgado and Morais. Empirically, we find that both the weight heuristic and the gate score heuristic perform better than directly exploiting vertex separators despite having no provable performance guarantee. We also provide some theoretical support for the weight heuristic of Delgado and Morais in finite automata with dense transition structures.