Матрица теоремы Майкла-Нерода для автоматов

Я успешно реализовал теорему Майхилла-Нероде в C ++. Когда это заканчивается, чтобы минимизировать данный автомат, матрица дана как ответ.

Используя автоматы на этой странице: 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, …), transitions — строковый вектор, содержащий имя каждого состояния, в которое могут перейти мои автоматы, final — логическое значение, указывающее если мое состояние является принимающим, а start — логическое значение, указывающее, является ли мое состояние начальным.

Например, для узла q0 данного автомата его структура будет выглядеть примерно так:

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

Моя проблема: мне нужно преобразовать эту матрицу в структуру автоматов, следуя приведенной структуре. Я легко могу определить начальные / конечные состояния, так как у меня есть исходная информация о автоматах, и я могу легко идентифицировать каждую из групп.

Что я не могу понять в матрице, так это переходы между группами. Какие-либо предложения?

1

Решение

Каждое состояние является членом некоторой группы, и для каждой группы у вас есть список состояний в группе. Чтобы найти переходы для группы G1, выберите одно из состояний S1 в группе, возьмите переходы для S1, и для каждого целевого состояния S2 найдите соответствующую группу G2. Множество всех G2, которые вы получаете, составляют переходы из G1. (Обратите внимание, что, поскольку все состояния в G1 эквивалентны, вам нужно рассмотреть только одно представительное состояние S1.)

1

Другие решения


По вопросам рекламы [email protected]