通用图灵机

接收(01)*语言的通用图灵机东北大学计算机科学与技术专业XXXC语言代码：#includestdio.h#includestring.hchars[50]=B1010101101100101110111010111001101101101101000;//接收语言(01)*的通用图灵机charrelief[9]=A00000000;//缓冲域charinput[1000];//输入域intE=0,B=0,C=0,D=0;//标记号intnum=0;//输入字符数intconstfinish=3;//结束状态intmain(){voidtran(char*,char,int*);inttest();while(1){//清零变量charc;inti;intmark=-1;E=B=C=D=0;num=0;for(i=1;i9;i++)relief[i]='0';input[0]='0';printf(请输入语言：);c=getchar();for(num=1;c!='\n';num++){tran(input,c,&num);//将输入数据转换成一进制input[num]='0';c=getchar();}input[num]='\0';while(mark==-1){mark=test();}if(mark==1)printf(机器接收该语言\n);elseprintf(机器拒绝该语言\n);}return0;}voidtran(char*a,charc,int*num){//进制转换，将十进制换算成一进制存入数组input[num]inti,m;m=c-47;for(i=1;i=m;i++){a[*num]='1';(*num)++;}}intget(char*a,intA,int*length){//确定编码a中符号A后面的状态,返回状态长度lengthinti,n;n=A+1;if(a[n]=='\0'){*length=0;return0;}for(i=0;a[n]!='0';i++,n++);*length=i;return0;}inttest(){voidmove(char*,int);intcompare();inti,length=0;intlength2=0,d;D=0;//清零标记D//复写标记B或E后的状态到缓冲区，并标记Dget(s,E,&length);D=length+1;for(i=0;ilength;i++)relief[i+1]='1';//复写C后面的符号到缓冲区D之后get(input,C,&length);for(i=0;ilength;i++)relief[D+i+1]='1';//匹配if(!compare())return0;//无法匹配，停机//清空缓存区，将E右移一个符号for(i=1;i9;i++)relief[i]='0';D=0;//清零标志Dget(s,E,&length);E=E+length+1;//用E后的符号代替C后的符号,并把E向后移动一个符号get(s,E,&length);get(input,C,&length2);d=length-length2;move(input,d);//将输入域扩充(d0)或缩减(d0)for(;length0;length--)input[C+length];//新符号替代旧符号//E移动到方向分量前get(s,E,&length);E=E+length+1;//按方向移动Cget(s,E,&length);//读取方向if(length==1){//左移for(;input[C-1]!='0';C--);if(C=0)C--;elsereturn0;//越过左输入带，停机}else{//右移//printf(!\n);get(input,C,&length);C=C+length+1;get(s,E,&length);if((input[C+1]=='\0')){//越过右输入带，添加结束符input[C+1]='1';input[C+2]='1';input[C+3]='1';input[C+4]='0';input[C+5]='\0';}}//将E后移到下一个qget(s,E,&length);E=E+length+1;//判断E后面的新标号是否为接收态get(s,E,&length);if(length==finish)return1;//接受elsereturn-1;//继续扫描}intcompare(){//前两位编码(q,a)比较,修改Einti=0,j=0,k=0,n=0,m=0;for(i=1;i50;i++){if(s[i-1]=='B'){//比较第一个五元组j=i;n=0;for(k=1;relief[k]==s[j];k++,j++){if(s[j]=='0'){n++;if(n==1)m=j;}if(n==2){E=m;return1;}}}if((s[i-1]=='0')&&(s[i]=='0')){//比较后续的五元组j=i+1;n=0;for(k=1;relief[k]==s[j];k++,j++){if(s[j]=='0'){n++;if(n==1)m=j;}if(n==2){E=m;return1;}}}}return0;}voidmove(char*a,intd){//扩大或缩小输入区长度intlength,i;length=strlen(input);if(d0){while(length-1C){input[length+d+1]='\0';input[length+d]=input[--length];}}if(d0){i=C;while(ilength){input[i+1]=input[i+2];i++;}}}程序截图：运行编辑器：VC++，CodeBlocks均可运行。