正如我在post中解释的那样,我正在做一个模拟不确定的有限自动机的任务。我从文件tarea4.in
中读取了此输入:
1
6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d
5
aaabcccc
aabbbbcdc
abbcdddcc
acdddddd
abc
输入的第一行是整数T,代表要评估程序的案例数。每个测试用例均以4个整数开头,第一个是自动机的状态数,第二个是自动机的过渡数,第三个数是初始状态,然后是最终状态数。然后是最终状态(在示例中,最终状态是2和5)。然后是F行,每行都有一个整数E,代表E是最终状态。
然后是N行(N是过渡的数量),每行具有2个整数和一个字符I,J和C,代表过渡的状态,即过渡从状态i到状态J的字符为C。该行之后是单个整数S,它将包含要测试的字符串数,然后是带有相应字符串的S行。
预期的输出是:
Test Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Accepted
abc Accepted
输出导致我的代码:
Test Case #1:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Rejected
abc Rejected
这是我的代码:
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <vector>
using namespace std;
typedef map<pair<int, int>, char> transitions;
transitions trans;
int numberFinals;
vector<int> currentStates;
int main (){
freopen ("tarea4.in", "r", stdin);
//freopen ("tarea4.out", "w", stdout);
int testCases, i, j,k, cont=1,finalStates,numberInputs,stateOrigin, stateDestination;
int numberStates, numberTransitions, initialState;
char transitionCharacter ;
set<int> current;
set<int> next;
set<int>::iterator it;
set <int> final;
std::set<int> the_intersection; // Destination of intersect
map<pair<int, int>, char>::iterator p;
string inputString;
cin>> testCases;
for (i=0;i< testCases;i++){
cin>>numberStates>>numberTransitions>>initialState>>numberFinals;
current.insert (initialState);
for (j=0;j<numberFinals;j++){
cin>>finalStates;
final.insert(finalStates);
}
for (j=0; j<numberTransitions;j++){
cin>> stateOrigin>>stateDestination>>transitionCharacter;
trans.insert(transitions::value_type(std::make_pair(stateOrigin, stateDestination), transitionCharacter ));
}
cin>>numberInputs;
cout<<"Test Case #"<<cont++<<":"<<endl;
for (j=0; j<numberInputs;j++){
//////////////////the code of the answer /////////////////
current.insert (initialState);
cin>> inputString;
cout<<inputString<<" ";
for (k=0; k<str.size();k++){
next.clear();
for ( it=current.begin() ; it != current.end(); it++ ){
for (q= trans.begin(); q!= trans.end();q++){
if((*it == q->first.first)&&(str[k]==q->second)){
next.insert(q->first.second);
}
current=next;
}
}
}
std::set_intersection(current.begin(), current.end(), final.begin(), final.end(), std::inserter(the_intersection, the_intersection.end()));
if (the_intersection.size()>0){
cout<< "Accepted"<<endl;
}
else{
cout<< "Rejected"<<endl;
}
}
printf ("\n");
}
return 0;
}
我的问题是:为什么我得到的输出不正确?我认为这是为了确定测试用例中自动机的不确定性,但是如何正确评估字符串呢?如何以某种方式将我的函数
evaluate_string
更改为ojit_code,以检查自动机可以通过非确定性来评估字符串的不同路径?我已经坚持了好几天,老实说,我有些绝望。
最佳答案
评估NFA与评估DFA几乎一样容易。
在DFA中,您拥有一个当前状态,并且在每个步骤中都选择下一个过渡。在输入末尾,您检查当前状态是否为接受状态。
好吧,在NFA中,您具有一组当前状态,并且在每个步骤中都要经历所有当前状态,并为每个状态选择所有有效的过渡。这些组合的集构成了您的新状态集。
最后,检查当前状态和接受状态的交集是否为非空。
在伪代码中,它看起来如下:
过渡中的每个
"String accepted"
"String rejected"
可以将其逐行转换为C++代码。为了简化此操作,我建议将
std::set<int>
用于current
和next
集,并使用std::multimap<char, int>
的 vector 进行过渡。假设每个状态对应一个整数。