CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
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");
}
}
}