自动机的Myhill-Nerode定理矩阵
自动机的Myhill-Nerode定理矩阵
提问于 2015-05-01 14:53:49
我在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 state{
public:
string state_name;
vector<string> transitions;
bool final;
bool start;
public:
state(string,vector<string>,bool,bool);
};其中，状态名称是我当前状态的名称(A，B，C，D，state1，.)，转换是一个字符串向量，包含我的自动机可以去的每个状态的名称，final是一个布尔值，指示我的状态是否是一个接受状态，start是一个布尔值，指示我的状态是否是一个开始状态。
例如，对于给定自动机的节点q0，其结构如下：
state_name: q0
transitions: (q1,q2) <- always following the alphabet order
final: false
start: true我的问题是:我需要按照给定的结构将这个矩阵转换成一个自动机结构。我可以很容易地识别起始/最终状态，因为我有原始的自动机信息，而且我可以很容易地识别每个组。
我在矩阵中找不到的是组间的转换。有什么建议吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-05-01 15:11:19
每个状态都是某个组的成员，对于每个组，您都有一个组中的状态列表。要查找组G1的转换，选择组中的状态S1之一，接受S1的转换，对于每个目标状态S2，查找相应的组G2。您获得的所有G2的集合构成了来自G1的转换。(请注意，由于G1中的所有状态都是等效的，所以只需要考虑一个具有代表性的状态S1。)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29989213
复制相关文章
相似问题
腾讯云开发者
