参考答案

正确答案：(1)设∑为字母表TAB为存放NFA的状态转移k为状态计数器t为已到达状态O为开始状态#为输入正规式的终止符号。k＝0；t＝0；st0＝0q＝0；a＝getc()；do{ while(a∈∑){ sym＝getc()；if(sym=="*"){ 将状态转移k＋1∈f(tε)k＋1∈f(k＋1a)k＋2∈f(k＋1ε)加入TAB中；k＝k＋2；t＝k；a＝getc()；}else{ 将状态转移k＋1∈f(ta)加入TAB表中；k＝k＋1；t＝k；a＝sym；}}while(a=="｜"){ if(q==0){ stl＝t；t＝st0；q＝1；}else{ 将状态转移stl∈f(tε)加入TAB表中；t＝st0；a＝getc()}}while(a=="("){ 将st0st1q压入STACK栈；将状态转移k＋1∈f(tε}加入TAB表中；k＝k+1；t＝kst0＝k；q＝0；a＝getc()；}while(a==")")( if(q==1){ 将状态转移stl∈f(tε)加入TAB表中t＝St1；}sym=getc()；if(Sym!="*")a＝Sym；elSe{ 将状态转移st0∈f(tε)k＋1∈f(st0ε)加入TAB表中；k＝k＋1；t＝k；a＝getc()；}弹出STACK顶端内容分别送人st0st1q；}}while(a!="#")if(q==1){ 将状态转移stl∈f(tE)加入TAB表中；t＝St1；}(2)先定义￡闭包和a弧转移两个函数。voidε__closure(xy){ 将状态集X中的状态逐个压人STACK栈；y＝X；do{ 弹出STACK顶端的状态s；for(对S经由￡弧到达的所有状态t){ if(t不在y中){ 将t压入STACK栈；y＝y∪{t}；}})while(STACK不空)}void Closure(xay){ 将集合X的状态逐个送人LINK链表中；r={}；do{取出LINK的链头项S；for(TAB表中的每一项f{sb)＝t}if(b=="ε")将t加到LINK链尾；elseif(b=="a")r＝r＋{t}}while(LINK不空)；if(r=={}}y＝{}elseε_closure(ry)；}确定化算法如下：置状态集Q及终态集Z为空；εclosure({0}y}；Q[0]＝y；n＝0；i＝0jwhile(i<＝n){ x＝Q[i]for(字母表乏中的每个字符a){ closure{xay)；if(y!＝Ф){ if(y不在Q中){ n＝n+1；Q[n]＝y；}将状态转移f(xa)＝y加入TAB表中；if(y中含有NFA的终态)将Y加入集合Z中；}}i＝i＋1；}π[1]＝Ф；π[2]＝Ф；for(状态集中的每个状态i)if(i是终态)π[2]＝π[2]＋{i}；elseπ[1]＝π[1]＋{i}m＝2；do{P＝m；i＝i；do{ for(所有a∈∑){ for(k=ij k<=m+Ij k++)πs[k]＝Ф；for(π[i]中的所有状态q)if(f(qa)==Ф)πs[m＋1]＝πs[m＋1]＋{q}；elseif(f(qa)==p}for(k＝0；k<＝m；k＋＋)if(p∈π[k])πs[k]＝πs[k]＋{P}；for(k＝ij＝0；k<＝m＋i；k＋＋)if(πs[k]!＝Фπs[＋＋j]＝πs[k]；if(j!＝1){ π[i]＝πs[1]；for(k＝1；k<＝j－1；k＋＋)π[m＋k]＝πs[k＋1]m＝m＋j；}}i＝i＋i；}while(i!＝m)；}while(p!＝m)；
设∑为字母表,TAB为存放NFA的状态转移,k为状态计数器,t为已到达状态,O为开始状态,#为输入正规式的终止符号。k＝0；t＝0；st0＝0q＝0；a＝getc()；do{while(a∈∑){sym＝getc()；if(sym=="*"){将状态转移k＋1∈f(t,ε),k＋1∈f(k＋1,a),k＋2∈f(k＋1,ε)加入TAB中；k＝k＋2；t＝k；a＝getc()；}else{将状态转移k＋1∈f(t,a)加入TAB表中；k＝k＋1；t＝k；a＝sym；}}while(a=="｜"){if(q==0){stl＝t；t＝st0；q＝1；}else{将状态转移stl∈f(t,ε)加入TAB表中；t＝st0；a＝getc(),}}while(a=="("){将st0,st1,q压入STACK栈；将状态转移k＋1∈f(t,ε}加入TAB表中；k＝k+1；t＝k,st0＝k；q＝0；a＝getc()；}while(a==")")(if(q==1){将状态转移stl∈f(t,ε)加入TAB表中,t＝St1；}sym=getc()；if(Sym!="*")a＝Sym；elSe{将状态转移st0∈f(t,ε),k＋1∈f(st0,ε)加入TAB表中；k＝k＋1；t＝k；a＝getc()；}弹出STACK顶端内容分别送人st0,st1,q；}}while(a!="#")if(q==1){将状态转移stl∈f(t,E)加入TAB表中；t＝St1；}(2)先定义￡闭包和a弧转移两个函数。voidε__closure(x,y){将状态集X中的状态逐个压人STACK栈；y＝X；do{弹出STACK顶端的状态s；for(对S经由￡弧到达的所有状态t){if(t不在y中){将t压入STACK栈；y＝y∪{t}；}})while(STACK不空)}voidClosure(x,a,y){将集合X的状态逐个送人LINK链表中；r={}；do{取出LINK的链头项S；for(TAB表中的每一项f{s,b)＝t}if(b=="ε")将t加到LINK链尾；elseif(b=="a")r＝r＋{t},}while(LINK不空)；if(r=={}}y＝{},elseε_closure(r,y)；}确定化算法如下：置状态集Q及终态集Z为空；εclosure({0},y}；Q[0]＝y；n＝0；i＝0jwhile(i<＝n){x＝Q[i],for(字母表乏中的每个字符a){closure{x,a,y)；if(y!＝Ф){if(y不在Q中){n＝n+1；Q[n]＝y；}将状态转移f(x,a)＝y加入TAB表中；if(y中含有NFA的终态)将Y加入集合Z中；}}i＝i＋1；}π[1]＝Ф；π[2]＝Ф；for(状态集中的每个状态i)if(i是终态)π[2]＝π[2]＋{i}；elseπ[1]＝π[1]＋{i},m＝2；do{P＝m；i＝i；do{for(所有a∈∑){for(k=ijk<=m+Ijk++)πs[k]＝Ф；for(π[i]中的所有状态q)if(f(q,a)==Ф)πs[m＋1]＝πs[m＋1]＋{q}；elseif(f(q,a)==p}for(k＝0；k<＝m；k＋＋)if(p∈π[k])πs[k]＝πs[k]＋{P}；for(k＝i,j＝0；k<＝m＋i；k＋＋)if(πs[k]!＝Фπs[＋＋j]＝πs[k]；if(j!＝1){π[i]＝πs[1]；for(k＝1；k<＝j－1；k＋＋)π[m＋k]＝πs[k＋1],m＝m＋j；}}i＝i＋i；}while(i!＝m)；}while(p!＝m)；