是否可将任意DFA转换为起始状态无入边的DFA？

对于任意给定的DFA，我们都能构造出一个等价的DFA，满足起始状态仅有出边、无任何入边的要求，具体构造方法如下：

• 如果原DFA的起始状态本身就没有入边：直接使用原DFA即可，无需修改。
• 如果原DFA的起始状态存在来自其他状态的入边：
  1. 新增一个全新的状态作为新的起始状态（记为S_new）。
  2. 对每个输入符号a，将S_new的a转移设置为与原起始状态（记为S_old）的a转移完全相同。
  3. 如果S_old是接受状态，那么S_new也需要设为接受状态（保证空串的接受性与原DFA一致）。
  4. 保留原DFA的所有其他状态、转移和接受状态不变。

这种构造出来的新DFA和原DFA接受完全相同的语言，同时新起始状态S_new没有任何入边——因为它是新增的状态，原DFA中没有任何状态的转移会指向它，也不会新增指向它的转移。

举个简单例子：假设原DFA的起始状态S有一个从状态A来的入边，输入b时A转移到S。我们新增S_new，让S_new的所有转移和S一样，若S是接受态则S_new也设为接受态。此时新DFA中，没有任何状态会转移到S_new，完全满足要求，且接受的语言和原DFA一致。

内容的提问来源于stack exchange，提问作者Pouya Kafashi