DFA 识别语言

Time Limit: 1sec Memory Limit:256MB

Description

对于给出的 DFA 和输入的字符串，判断字符串是否是 DFA 识别的语言。

Input

输入有多组数据。每组数据的第一行是两个整数 N（N<=50）和 M（M<=26），分别代表 DFA 的状态数和字母表的字符数。DFA 的 N 个状态用整数 0 ～ N-1 表示。状态 0 为起始状态。字母表包含的字符是小写英文字母的前 M 个字符。接下来的 N 行，每行有 M 个整数。其中第 i 行第 j 列的数字 k，表示 DFA 在状态 i-1，当输入符号为第 j 个小写字母时，迁移到状态 k。接下来的一行包含若干个整数，代表 DFA 的接受状态，这一行以-1 结尾。接下来的每一行是一个待识别的字符串，字符串的长度在 1 到 50 之间且只含有小写字母。字符串”#”代表本组数据结束。N=M=0 表示输入结束。

Output

对于每个待识别的字符串，如果能被给出的 DFA 识别，输出 YES；否则输出 NO。

Sample Input

4 2
1 0
1 2
1 3
1 0
3 -1
aaabb
abbab
abbaaabb
abbb
#
1 3
0 0 0
0 -1
cacba
#
0 0

Sample output

YES
NO
YES
NO
YES

Hint

你只需要实现课本 Figure 3.27 的程序就可以。

Solution

#include <bits/stdc++.h>
using namespace std;
struct DeterministicFiniteAutomaton
{
    struct State
    {
        vector<int> trans;
        int isAccepted;
        State(int m) : trans(m, -1), isAccepted(0) {}
    };
    vector<State> state;
    DeterministicFiniteAutomaton(int n, int m) : state(n, State(m)) {}
    int ask(const string &s)
    {
        int cur = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            cur = state[cur].trans[s[i] - 'a'];
            if (cur < 0)
                return 0;
        }
        return state[cur].isAccepted;
    }
};
int main()
{
    for (int n, m; cin >> n >> m && n && m;)
    {
        DeterministicFiniteAutomaton dfa(n, m);
        for (int i = 0, k; i < n; ++i)
            for (int j = 0; j < m; ++j)
            {
                cin >> k;
                dfa.state[i].trans[j] = k;
            }
        for (int k; cin >> k && k >= 0;)
            dfa.state[k].isAccepted = 1;
        for (string s; cin >> s && s != "#";)
            cout << (dfa.ask(s) ? "YES\n" : "NO\n");
    }
}

NFA 识别语言

Time Limit: 1sec Memory Limit:256MB

Description

对于给出的 NFA 和输入的字符串，判断字符串是否是 NFA 识别的语言。

Input

输入有多组数据。每组数据的第一行是两个整数 N（N<=50）和 M（M<=27），表示 NFA 有 N 个状态，以及字母表有 M-1 个字符。NFA 的 N 个状态用整数 0 ～ N-1 表示，状态 0 为起始状态。字母表包含小写英文字母的前 M-1 个字符。接下来的 N 行，每行有 M 个整数集（用’{‘和’}’括起）。其中，第 i 行第 1 列的整数集表示在状态 i-1 时，对应于 є（空串）的状态迁移；第 i 行第 j（j>1）列的整数集，表示 NFA 在状态 i-1，当输入符号为第 j-1 个小写字母时，迁移到的状态集。接下来的一行包含若干个整数，代表 NFA 的接受状态，这一行以-1 结尾。接下来的每一行是一个待识别的字符串，字符串的长度在 1 到 50 之间且只含有小写字母。字符串”#”代表本组数据结束。N=M=0 表示输入结束。

Output

对于每个待识别的字符串，如果能被给出的 NFA 识别，输出 YES；否则输出 NO。

Sample Input

4 3
{} {0,1} {0}
{} {} {2}
{} {} {3}
{} {} {}
3 -1
aaabb
abbab
abbaaabb
abbb
#
0 0

Sample Output

YES
NO
YES
NO

Hint

输入样例是课本 Figure 3.24 的 NFA。你需要实现的是课本 Figure 3.33 和 3.37 的算法。

Solution

#include <bits/stdc++.h>
using namespace std;
struct NondeterministicFiniteAutomaton
{
    struct State
    {
        vector<vector<int>> trans;
        int isAccepted;
        State(int m) : trans(m), isAccepted(0) {}
    };
    vector<State> state;
    NondeterministicFiniteAutomaton(int n, int m) : state(n, State(m)) {}
    vector<vector<int>> vis;
    int ask(const string &s, int i = 0, int cur = 0)
    {
        if (vis[i][cur])
            return 0;
        vis[i][cur] = 1;
        if (i == s.size() && state[cur].isAccepted)
            return 1;
        for (int j : state[cur].trans.back())
            if (ask(s, i, j))
                return 1;
        if (i < s.size())
            for (int j : state[cur].trans[s[i] - 'a'])
                if (ask(s, i + 1, j))
                    return 1;
        return 0;
    }
};
int main()
{
    for (int n, m; cin >> n >> m && n && m;)
    {
        NondeterministicFiniteAutomaton dfa(n, m);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
            {
                string s;
                cin >> s;
                int x = -1;
                for (int k = 1; k < s.size(); ++k)
                {
                    if (isdigit(s[k]))
                    {
                        if (x < 0)
                            x = 0;
                        x = x * 10 + s[k] - '0';
                    }
                    else if (x >= 0)
                    {
                        dfa.state[i].trans[(j + m - 1) % m].push_back(x);
                        x = -1;
                    }
                }
            }
        for (int k; cin >> k && k >= 0;)
            dfa.state[k].isAccepted = 1;
        for (string s; cin >> s && s != "#";)
        {
            dfa.vis.assign(s.size() + 1, vector<int>(n, 0));
            cout << (dfa.ask(s) ? "YES\n" : "NO\n");
        }
    }
}