css - FSA 接受的无 epsilon 转换的语言联盟

Question

我一直在尝试在不使用 epsilon 转换的情况下形式化两个有限状态自动机的并集。我想为新的自动机创建一个新的初始启动状态，并从这个新的启动状态通过复制这些转换从单独的自动机的启动状态创建到可到达状态的转换。

给定一个 FSA

M1 = <Σ1, Q_1, q0_1, ->_1> 

其中 Σ1 = 字母表，Q_1 是状态集，q0_1 是起始状态，->_1 是 M1 的转换。

给定另一个 FSA

 M2 = <Σ2, Q_2, q0_2, ->_2>  

其中 Σ2 是字母表，Q_2 是状态集，q0_2 是起始状态，->_2 是 M2 的转换。

现在我已经定义了 FSA M+ = M1 ∪ M2 作为 FSA :

 M_+ = <Σ+, Q_+, q0_+, ->_+>
 Σ+ = Σ1 ∪ Σ2 - alphabet of both
 Q_+ = Q_1 ∪ Q_2 ∪ {q0_+},
 q0+ is the new initial start state 
 ->_+ = ->_1 ∪ ->_2 ∪ ->_C

我一直在定义 ->_C 时遇到问题 - 到 M1 和 M2 可达状态的新转换。我将 ->_C 的类型定义为:Q x 2^Σ x 2^Q。它必须是一个集合，但我不确定如何正式定义它。非常感谢任何帮助。

Answer 1

为什么是 Q x 2^Σ x 2^Q ？更好的 Q x Σ x 2^Q；转换是为每个可能的字母单独定义的。否则你不知道哪个状态属于哪个字母。

->C := { (q0+,x,P) : (q0_1,x,P)\in ->_1 或 (q0_2,x,P)\in ->_2