Myhill-Nerode 定理矩阵到自动机

Question

我已经在 C++ 中成功实现了 Myhill-Nerode 定理。当它完成最小化给定自动机时，给出一个矩阵作为答案。

使用此页面上的自动机：http://web.stcloudstate.edu/pkjha/CSCI502/Minimize.html，我得到了最终矩阵（这是给定矩阵的完整矩阵，而不是下三角矩阵）：

- x x x x x x x x 
x - - x x x x x x 
x - - x x x x x x 
x x x - - - - x x 
x x x - - - - x x 
x x x - - - - x x 
x x x - - - - x x 
x x x x x x x - - 
x x x x x x x - -

也就是说第1,2,4,8行都是不同的状态，第(1),(2,3),(4,5,6,7),(8,9)行可以被分到同一个州。

我正在使用 class 来表示根据此结构的自动机的每个状态：

class state{
    public:
        string state_name;        
        vector<string> transitions; 
        bool final;                
        bool start;            
    public:
        state(string,vector<string>,bool,bool);
};

其中，state name 是我当前状态的名称（A，B，C，D，state1，...），transitions 是一个字符串向量，包含我的自动机可以进入的每个状态的名称， final 是一个布尔值，指示我的状态是否为接受状态，而 start 是一个布尔值，指示我的状态是否为开始状态。

例如，对于给定自动机的节点 q0，其结构类似于：

state_name: q0
transitions: (q1,q2) <- always following the alphabet order
final: false
start: true

我的问题是：我需要按照给定的结构将这个矩阵转换成自动机结构。我可以很容易地识别 starting/final 个状态，因为我有原始的自动机信息，而且我可以很容易地识别每个组。

我在矩阵中想不通的是组之间的转换。有什么建议吗？

Answer 1

每个州都是某个组的成员，对于每个组，您都有一个组中的州列表。要找到组 G1 的转换，请选择组中的状态 S1 之一，获取 S1 的转换，并为每个目标状态 S2 找到相应的组 G2。您获得的所有 G2 的集合构成了 G1 的转换。（注意，因为G1中的所有状态都是等价的，所以只需要考虑一个代表状态S1即可。）

Myhill-Nerode 定理矩阵到自动机

Myhill-Nerode theorem matrix to automata

c++

automata

dfa