编译原理不确定有穷自动机的确定化.
编译原理实验报告
实验三
安徽大学计算机科学与技术学院
1， 实验名称
不确定有穷自动机的确定化。
2， 实验目的
不确定有穷自动机的确定化。
3， 实验原理
1.NFA：
一个不确定的有穷自动机M是一个五元组，M=(K,E,f,S,Z)其中
a. K是一个有穷集，它的每个元素称为一个状态；
b. E是一个有穷字母表，它的每个元素称为一个输入符号；
c. f是一个从K×E*到K的子集的映像，即：K*E*->2k，其中2k表示K的幂集；
d. S包含于K，是一个非空初态集；
e. Z包含于K，是一个终态集。
2.DFA：
一个确定的有穷自动机M是一个五元组，M=(K,E,f,S,Z)其中
a. K是一个有穷集，它的每个元素称为一个状态；
b. E是一个有穷字母表，它的每个元素称为一个输入符号；
c. f是转换函数，是K×E->K上的映像，即，如f(ki,a)=kj(ki∈K,kj∈K)就意味着，当前状态为ki，输入字符为a时，将转换到下一状态kj，我们把kj称作ki的一个后继状态；
d. S∈K，是唯一的一个初态；
e. Z包含于K，是一个终态集，终态也称可接受状态或结束状态。 3，正规式
正规式是一种表示正规集的工具，正规式是描述程序语言单词的表达式，对于字母表∑其上的正规式及其表示的正规集可以递归定义如下。
① ε是一个正规式，它表示集合L(ε)={ε}。
② 若a是∑上的字符，则a是一个正规式，它所表示的正规集L(a)={a}。 ③ 若正规式r和s分别表示正规集L(r)、L(s)，则
（a）r|s是正规式，表示集合L(r)∪L(s)；
（b）r·s是正规式，表示集合L(r)L(s)；
（c）r*是正规式，表示集合(L(r))*；
（d）(r)是正规式，表示集合L(r)。
仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。
运算符“|”、“·”、“*”分别称为“或”、“连接”和“闭包”。在正规式的书写中，连接运算符“·”可省略。运算符的优先级从高到低顺序排列为：“*”、“·”、“|”。
运算符“|”表示“或”、并集。“*”表示*之前括号里的内容出现0次或多次。
若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规集U和V记作U=V。
4. 实验思路
1.状态集合I的空闭包closure（I），定义为一个状态集。
算法：
遍历I集合中的每一个元素，对于每一元素遍历所有的边，若该元素在NFA中连接到空边，则获取空边另一端的元素，判断元素是否在I中，若不在I中，则加入I，直到遍历结束。
2.确定化
算法：
A．找到NFA的开始符S，对开始符求closure（S），并创建集合T
并T（0）=closure（{S}）
B．找到T中未被标记的集合T1，若未找到，
C．对T1中，每一元素，执行函数F
D．执行步骤B
函数F：
A．对于T1中的每一元素a，找到每一元素在NFA同一类型的边所对应的元素c，把所有的c都放在集合C中，对于C求C=closure（C）。判断C是否在T中，若不在，则把C加入T。，记录T1->C的边，
B．执行A，知道把所有不同类型的边遍历为止。
3.构造DFA
a.对于集合In，选出集合In的每一I，在I中选出一个元素代表该集合，构造新的DFA
5. 实验小结
实验算法清晰，简单，只要是对于每一集合反复求closure闭包比较麻烦。程序循环，判断，标志位特别多。很容易出错。对于程序的内存管理更要小心，不要内存越界。
同时，我用的code blocks 编译器问题很大。当程序代码超过一定量、内存分配的数目和空间比较多的时候，对于内存的管理就会出现难以预料的错误。比如在程序开头分配了一段内存，在程序的末尾要使用该内存给其他变量赋值时，就会导致程序崩溃。
6. 实验截图
课本P58图4.4
输入
输出
附件
#include
#include
#include
char nfa[25][4];
struct list
{
char a[20];
int b;
char c;
int a_n;
} ;
struct list t[20];
int n; /*number of NFA edage*/
int main()
{
printf("鉏飞祥E21414018\n");
int cg=3;
printf("请输入每条边和节点\n例如：1a8表示0从1边到8，*代表空边以/结束输出\n");
void closure(int n);
char u[20];
int ed[20][4];
int n_ed=0;
n=0;
int n_t=0;/*number of T */
int i=0;
int k=1;
int j;
while(1)
{
scanf("%s",nfa[i]);
if(nfa[i][0]=='/')
break;
i++;
n++;
}
t[0].a[0]=nfa[0][0];
for(i=0;i
{
if(nfa[i][0]==nfa[0][0])
{
if(nfa[i][1]=='*')
附件
#include
#include
#include
char nfa[25][4];
struct list
{
char a[20];
int b;
char c;
int a_n;
} ;
struct list t[20];
int n; /*number of NFA edage*/
int main()
{
printf("鉏飞祥E21414018\n");
int cg=3;
printf("请输入每条边和节点\n例如：1a8表示0从1边到8，*代表空边以/结束输出\n");
void closure(int n);
char u[20];
int ed[20][4];
int n_ed=0;
n=0;
int n_t=0;/*number of T */
int i=0;
int k=1;
int j;
while(1)
{
scanf("%s",nfa[i]);
if(nfa[i][0]=='/')
break;
i++;
n++;
}
t[0].a[0]=nfa[0][0];
for(i=0;i
{
if(nfa[i][0]==nfa[0][0])
{
if(nfa[i][1]=='*')
t[0].a[k]=nfa[i][2];
k++;
}
}
}
t[0].a_n=k;
t[0].a[k]='\0';
n_t++;
t[0].b=0;
closure(0);
char temp;
for(i=0;i
for(j=0;;j++)
{
if(t[i].a[j]=='\0')
break;
for(k=j+1;;k++)
{
if(t[i].a[k]=='\0')
break;
if(t[i].a[k]
{
temp=t[i].a[k];
t[i].a[k]=t[i].a[j];
t[i].a[j]=temp;
}
}
}
int u_i;
int nn=n_t;
while(1)
{
u_i=0;
int bo=0;
int t_i;
for(t_i=0;t_i
{
if(t[t_i].b==0)
{
t[t_i].b=1;
bo++;
break; over*/
} if(bo==0) break; char a='a'; int cc=cg; /*有几条不同的边*/ while(cc--) { u_i=0; for(i=0;i
{ u[u_i]=nfa[j][2]; u_i++; } } } u[u_i]='\0'; char temp; for(i=0;i
}
a++;
}
nn++;
}
for(i=0;i
t[i].c=t[i].a[i];
printf("用 %c 代表 %s\n",t[i].c,t[i].a); } for(i=0;i
{
printf("%c-%c-%c\n",t[ed[i][0]].c,ed[i][1],t[ed[i][2]].c);
}
}
void closure(int nn)
{
int i,j,k;
int ii,jj;
for(i=0;i
for(j=0;j
{
if(t[nn].a[i]==nfa[j][0])
if(nfa[j][1]=='*')
{
int b=0;
for(ii=0;ii
if(t[nn].a[ii]==nfa[j][2]) b=1;
}
if(b==0)
{
t[nn].a[t[nn].a_n]=nfa[j][2]; t[nn].a_n++;
}
}
}
t[nn].a[t[nn].a_n]='\0';
}