7

正如我在这篇文章中解释的那样，我正在做一个模拟非确定性有限自动机的任务。我从文件中读取了这个输入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以某种方式将调用的函数更改为检查可以使自动机通过非确定性评估字符串的不同路径？

我已经坚持了好几天了，老实说，我有点绝望。

4

3 回答 3

10

评估 NFA几乎与评估 DFA一样容易。

在 DFA 中，您有一个当前状态，并且在每个步骤中您选择下一个转换。在输入结束时，您检查当前状态是否为接受状态。

好吧，在 NFA 中，您有一组当前状态，并且在每个步骤中，您都会遍历所有当前状态，并且为每个状态选择所有有效转换。这些组合集形成了您的新状态集。

最后，检查当前状态和接受状态的交集是否为非空。

在伪代码中，如下所示：

  • 当前= {初始}
  • 对于输入中的每个字符 ：
    • 下一个= { }
    • 对于当前的每个状态 ：
      • 对于 transitions [ state ][ char ] ∪ transitions [ state ][ ϵ ]中的每个 转换：
        • 接下来。附加（target_of（过渡））
    • 当前=下一个
  • 如果 len (交点(当前,接受)) > 0:
    • 打印 "String accepted"
  • 否则：
    • 打印 "String rejected"

这可以逐行翻译成 C++ 代码。为方便起见，我建议使用std::set<int>forcurrent和next集合，使用向量 ofstd::multimap<char, int>进行转换。这假设每个状态对应一个整数。

于 2012-05-17T10:13:37.960 回答
1

根本问题是，一旦您找到第一个有效转换，您的代码就会跳出转换循环。如果您正在执行 DFA，这会起作用，但 NFA 可能有多个有效路径。

你有两个选择（我相信还有更多）：

1) 实现 NFA 评估器：这涉及跟踪一组当前状态，并针对每个状态评估每个输入字符。一旦字符串被读取，如果任何最终状态都在集合中，则它是完整的。

2) 将 NFA 转换为 DFA，恕我直言，这是一种更难的方法，因为这基本上涉及构建相同的集合逻辑并评估新状态的转换。

于 2012-05-16T22:15:38.767 回答
1

我认为您应该首先实现将任何 NFA 转换为其相应 DFA 的通用机制。之后，您可以轻松实现自动运行程序，因为 DFA 可以确定地工作。

于 2012-05-16T21:16:37.013 回答