On the Gap Between Separating Words and Separating Their Reversals

Farzam Ebrahimnejad

A deterministic finite automaton (DFA) separates two strings $w$ and $x$ if it accepts $w$ and rejects $x$. The minimum number of states required for a DFA to separate $w$ and $x$…