FA进阶2 7-1 DFA等价状态的合并
题目详情:
题目链接:https://pintia.cn/problem-sets/1632722166296961024/exam/problems/1632722240368369664
思考:
首先是输入:我们对于所有的状态,都认为只有0-9和所有的大小写字母,但其实对于状态来说是可以存在10以上的状态,
我们这里不考虑,而且题目的测试案例也没有这样的。
在输入的时候我们需要收集初态、终态、以及非终态集,
因为我们使用分割法首先是需要将所有的状态分割成非终态集合终态集,
需要注意的是,初态也可能是终态,所以在输入的时候不要直接把初态收集到了非终态集了。
按照惯例,我们还是用邻接表来存这个非最小化的DFA,而对于产生的DFA,我们会用新的邻接表来存。
然后就是核心的分割法算法了,我们用队列来存当前可能需要分割的集合,如果这个集合经过所有的输入字符得到的输出都在一个集合中,那么就说明这个集合已经分割完全了,可以直接插入到最小化的dfa了。(代码中用sign来表示这样的情况)
如果这个集合经过输入字符得到的输出不在一个集合中,那么就说明这个集合还需要根据输出进行分割然后将分割得到的集合压入到队列中。
需要注意的是,如果一个状态经过输入字符得到的是空集,即没有对应的边弧,那么这样也是得到了与其他集合相比较不同的集合,需要分割。
而对于集合的处理,如何找到一个字符对应的集合是什么,如何匹配两个字符之间,多个字符之间对应的集合,这就需要用到并查集了
我们在最开始就把并查集初始化,即p[i]=i,在我们往队列中插入集合时,我们就需要将这个集合中将所有字符的祖宗结点都改为第一个字符,p[s[i]]=p[s[0]],只要找到祖宗结点,就可以区分这个集合了。
我们在得到这个集合通过输入字符的输出的时候,就需要先得到这个输出中包含的集合的个数,如果这个个数
大于1,则说明这个集合需要被分割,用vector和unordered_set来存这个输出对应的集合的祖宗结点,这样即可以得到个数又可以方便的查找当前的字符是不是和要分割的集合对应的(用count)。
需要注意的是,如果得到的是空集,我们在代码中用sign_empty来表示这个情况,我们就需要将这个字符对应的集合设为-1。
在将分割出来的集合插入到队列中的时候,我们又要将所有的字符的祖宗结点赋值为第一个字符但需要注意的是,我们在这个集合还没有完全走完所有输入字符的时候,是不能改动并查集的,那么我们就需要用一个备份的并查集(这个备份的并查集是用来记录原来的状态的),用这个备份的来匹配就没事了,来修改,等,等这个集合经过所有的集合之后,我们再将备份的这个原封不动的放回到原来的并查集去。
最后得到所有的分割完全的集合之后,然后就可以开始建立最小化的DFA的邻接表了,同样用并查集
来匹配集合,这样就做完了(累.jpg)。
下面是一些案例:
输入样例1:
2
a b
0
1
3
8
0 a 1
0 b 2
1 a 1
1 b 3
2 a 1
2 b 2
3 a 1
3 b 3
输出样例1:
0 a 1
0 b 0
1 a 1
1 b 2
2 a 1
2 b 2
2
输入样例2:
2
a b
0
1
4
10
0 a 1
0 b 2
1 a 1
1 b 3
2 a 1
2 b 2
3 a 1
3 b 4
4 a 1
4 b 2
输出样例2:
0 a 1
0 b 0
1 a 1
1 b 2
2 a 1
2 b 3
3 a 1
3 b 0
3
输入样例3(教材P65 T9):
4
a b c d
1
2
6 7
13
1 a 3
1 b 2
2 a 4
2 b 2
3 b 6
3 c 3
3 d 5
4 b 7
4 c 3
4 d 5
5 a 4
6 b 6
7 b 6
输出样例3:
0 a 1
0 b 0
1 b 3
1 c 1
1 d 2
2 a 1
3 b 3
3
输入样例4(输入样例2改)(初态可能是终态):
2
a b
0
2
0 4
10
0 a 1
0 b 2
1 a 1
1 b 3
2 a 1
2 b 2
3 a 1
3 b 4
4 a 0
4 b 2
输出样例4:
0 a 1
0 b 2
1 a 1
1 b 3
2 a 1
2 b 2
3 a 1
3 b 4
4 a 0
4 b 2
0 4
输入样例5(输入字符有4个,初态是终态,终态有3个):
4
a b c d
1
3
1 6 7
13
1 a 3
1 b 2
2 a 4
2 b 2
3 b 6
3 c 3
3 d 5
4 b 7
4 c 3
4 d 5
5 a 4
6 b 1
7 b 6
这个输入样例5我好像有问题,但提交上去是100分,所以我就没管了。
最后是具体的代码:
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1010;
unordered_set<char> not_final_state;//非终态
unordered_set<char> final_state_set;//终态
vector<string> T;//最小化的dfa;
string not_final_state_string;//非终态
string final_state;//终态
string character;//输入字符
char initial_state;//初态
//邻接表
int h[N],ne[N],idx;
char e[N],w[N];
int p[N];//并查集
int p_last[N];//并查集的镜像
vector<string> initial_string;//最小DFA的初态
vector<string> final_string;//最小DFA的终态
vector<int> final_string_int;//最小DFA的终态,存的是在T中的下标
int h_m[N],ne_m[N],e_m[N],idx_m;
char w_m[N];
void cin_init();
void add(char a,char b,char c)
{
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
void add_m(int a,int b,char c)
{
e_m[idx_m]=b;
ne_m[idx_m]=h_m[a];
w_m[idx_m]=c;
h_m[a]=idx_m++;
}
int find(string s,char c)
{
for(int i=0;i<s.size();i++)
{
if(s[i]==c)return i;
}
return -1;
}
int find_T(vector<string> v,string s)
{
for(int i=0;i<v.size();i++)
{
if(v[i]==s)return i;
}
return -1;
}
void set_gathering(string s)
{
p_last[s[0]]=s[0];
for(int i=1;i<s.size();i++)
p_last[s[i]]=p_last[s[i-1]];
}
void generating_min_dfa()
{
//初始化并查集
for(int i=0;i<N;i++)
p[i]=i;
queue<string> q;
//一开始是加入非终态和终态
q.push(not_final_state_string);
for(int i=1;i<not_final_state_string.size();i++)//划分集合
p[not_final_state_string[i]]=p[not_final_state_string[i-1]];
// set_gathering(not_final_state_string);
q.push(final_state);
for(int i=1;i<final_state.size();i++)//划分集合
p[final_state[i]]=p[final_state[i-1]];
// set_gathering(final_state);
// cout<<not_final_state_string<<" "<<final_state<<endl;
while(q.size())
{
string t=q.front();
q.pop();
int sign=1;//表示这个集合没有被分解
for(int j=0;j<character.size();j++)//遍历输入字符集合
{
string middle_result;
unordered_set<int> out_cnt_set;//用来存下面这个循环出现的有关集合,size表示个数
vector<int> out_cnt_vector;
for(int i=0;i<t.size();i++)//遍历这个集合
{
int sign_empty=0;
for(int k=h[t[i]];k!=-1;k=ne[k])//找到对应的边
{
if(w[k]==character[j])
{
middle_result+=e[k];
if(!out_cnt_set.count(p[e[k]]))
{
out_cnt_set.insert(p[e[k]]);
out_cnt_vector.push_back(p[e[k]]);
}
sign_empty=1;
break;
}
}
//如果没有这条弧,即得到的是空集
if(!sign_empty)
{
char l='@';
middle_result+=l;
p[l]=-1;
if(!out_cnt_set.count(p[l]))
{
out_cnt_set.insert(p[l]);
out_cnt_vector.push_back(p[l]);
}
}
}
// cout<<"p:"<<endl;
// for(int i=0;i<middle_result.size();i++)
// {
// cout<<p[middle_result[i]]<<" ";
// }
// cout<<endl;
if(out_cnt_set.size()==1)continue;//只出现了一个集合
else
{
memcpy(p_last,p,sizeof(p));
//出现了两个及两个以上的集合,需要进行分离
for(int i=0;i<out_cnt_vector.size();i++)
{
int number = out_cnt_vector[i];//当前需要分割成的集合
string insert_string;//需要插入的string
for(int k=0;k<middle_result.size();k++)
{
if(p[middle_result[k]]==number)
{
insert_string+=t[k];//注意这里应该是t
}
}
sort(insert_string.begin(),insert_string.end());
set_gathering(insert_string);
q.push(insert_string);
// cout<<insert_string<<" ";
}
// cout<<endl;
memcpy(p,p_last,sizeof(p_last));
sign=0;
break;
}
}
if(sign)
{
T.push_back(t);
// 同时判断以下这个是不是初态或者终态
// 判断初态
if(find(t,initial_state)!=-1)initial_string.push_back(t);
//判断终态
for(int i=0;i<final_state.size();i++)
{
if(find(t,final_state[i])!=-1){final_string.push_back(t);break;}
}
}
}
sort(T.begin(),T.end());
for(int i=0;i<final_string.size();i++)
final_string_int.push_back(find_T(T,final_string[i]));
sort(final_string_int.begin(),final_string_int.end());
for(int i=0;i<T.size();i++)
{
cout<<"i="<<i<<" "<<T[i]<<endl;
}
cout<<"T.size="<<T.size()<<endl;
}
void handle_min_dfa()
{
// 初始化并查集
for(int i=0;i<T.size();i++)
{
for(int j=0;j<T[i].size();j++)
p[T[i][j]]=i;
}
memset(h_m,-1,sizeof(h_m));
for(int i=0;i<T.size();i++)
{
string t=T[i];
char t1=t[0];//由于最小DFA中无论是谁走,走到的集合都是一样的,所以随便拿一个就好
for(int j=0;j<character.size();j++)
{
char op=character[j];
for(int k=h[t1];k!=-1;k=ne[k])
{
if(w[k]==op)
{
int target=p[e[k]];
add_m(i,target,op);
break;
}
}
}
}
for(int i=0;i<T.size();i++)
{
string a;
for(int j=h_m[i];j!=-1;j=ne_m[j])
{
string b;
b+=to_string(i)+" "+w_m[j]+" "+to_string(e_m[j])+"\n";
a=b+a;
}
cout<<a;
}
for(int i=0;i<final_string_int.size();i++)
{
cout<<final_string_int[i];
if(i!=final_string_int.size()-1)cout<<" ";
}
}
int main()
{
cin_init();
generating_min_dfa();
handle_min_dfa();
return 0;
}
void cin_init()
{
int n;char c;
//输入符号
scanf("%d",&n);
for(int i=0;i<n;i++)
{
cin>>c;character+=c;
}
//初态
cin>>initial_state;
// not_final_state.insert(initial_state);//初态可能是终态
// not_final_state_string+=initial_state;
//终态
scanf("%d",&n);
for(int i=0;i<n;i++)
{
cin>>c;final_state+=c;
final_state_set.insert(c);
}
//转换函数
scanf("%d",&n);
memset(h,-1,sizeof(h));
for(int i=0;i<n;i++)
{
char a,b;
cin>>a>>c>>b;
add(a,b,c);
// 既不是终态,又不是已经插入过的状态
if(!final_state_set.count(a)&&!not_final_state.count(a))
{
not_final_state_string+=a;
not_final_state.insert(a);
}
if(!final_state_set.count(b)&&!not_final_state.count(b))
{
not_final_state_string+=b;
not_final_state.insert(b);
}
}
//对终态和非终态集排序
sort(not_final_state_string.begin(),not_final_state_string.end());
sort(final_state.begin(),final_state.end());
// cout<<"终态:"<<final_state<<endl;
// cout<<"非终态:"<<not_final_state_string<<endl;
}
