x+1图灵机文档

设计一个图灵机，实现二进制数x的加1运算，同时保存进位。最高位如

果有进位的话可以保存该进位。

二、实现思路

1、图灵机设计：

图灵机M是一个七元组，M=（Q，∑，Γ，δ，q0，B，F），Q：状态的有穷集合；∑⊆Γ-｛B｝为输入字母表；Γ：带符号表； q0：q0∈Q是M的开始状态； B：B∈Γ称为空白符；F：F∈Q是终止状态集合；δ：M的转换函数。

在该x+1图灵机中，开始状态为s，终止状态为f，状态集合Q为{s,A,B,f}，空白符为*，字母表为{0,1}，进位标志位c，状态转移函数如下：

状态A：表示无进位的加法；状态B：表示有进位加法 状态转移函数为：

δ（s,0）=(A,1,L) c=0 δ（s,1）=(B,0,L) c=1 δ（A,0）=(A,0,L) c=0 δ（A,0）=(A,1,L) c=0 δ（B,0）=(A,1,L) c=0 δ（B,1）=(B,0,L) c=1 δ（A,*）=(f,*,R)

2、实现过程

初始化图灵机，分别初始化数据带为*0，这样结束符就是*，最左端的0是为了接收最高位的进位，如果有溢出的话直接丢弃可能使得计算结果不正确。然后是接收输入二进制数x，将该数据初始化到图灵机数据带上。初始化状态带为初始状态s，初始化进位标志位0。然后就是按照状态转移函数开始执行，修改数据带，状态带，和进位标志，遇到最左端的*时终止图灵机的执行，同时输出此时图灵机的数据带数据，和状态带状态，以及进位标志位，最后输出计算结果。

三、实现程序

#include

#include #include #define MAX_num 100

char x[MAX_num]; char str[MAX_num]; char s[4]=\"s\";

int c=0;//进位标志位

/*状态个数：4；状态名： S,A,B,F; 字母表：0,1,*; 状态说明：

s：表示初始状态 A：表示为进位状态 B：表示有进位状态 f：表示结束状态 字母表说明：

0,1，*，都是课识别的字符，其中*表示结束字符 */

void show(char str[],char s[],int c) {

printf(\"\\n运算之后图灵机状态 \\n\"); printf(\"\\n运算结束时状态：%s\

printf(\"\\n运算结束时数据带：%s\\n\ printf(\"运算结束时进位标志：%d\\n\\a\}

void Fun_A(char s[],char str[],int c,int n)//无进位加法状态转移函数 {

if(str[n-1]=='0'&&(str[n]=='0'||'1')) Fun_A(s,str,c,n-1); else if(str[n-1]=='*') { strcpy(s,\"f\"); show(str,s,c); } }

void Fun_B(char s[],char str[],int c,int n)//有进位加法状态转移函数 {

if(str[n]=='0') { str[n]='1'; strcpy(s,\"A\"); c=0; Fun_A(s,str,c,n-1); }

else if(str[n]=='1') { str[n]='0'; Fun_B(s,str,c,n-1); } }

void show_x(char str[],char x[])//，输出最后计算结果，即将数据带字符数组中的数值复制给x

{

int i=0,j=0;

int n=strlen(str)-2; while(j<=n) { if(str[j]=='1') x[i++]='1'; else if(str[j]=='0') x[i++]='0'; j=j+1; }

x[i]='\\0';

printf(\"\\n\\n运算结果 x:\"); printf(\"%s\\n\ }

void init(int n,char str[]){//初始化图灵机

int i=0; while(istrcat(str,\"*\");

printf(\"\\n初始化图灵机：\\n\\n\"); printf(\"初始化状态：%s\

printf(\"\\n初始化数据带：%s\\n\ printf(\"初始化进位标志：%d\\n\}

void start(int n){ //执行开始函数

if(str[n]=='0') { strcpy(s,\"A\"); str[n]='1'; c=0; Fun_A(s,str,c,n-1); }

else if(str[n]=='1') { strcpy(s,\"B\"); str[n]='0'; c=1; Fun_B(s,str,c,n-1); } }

int main () {

int b=1; int i=0; int n;

x[0]='\\0';//初始化x字符数组，也就是存放要进行加1运算的字符的数组 printf(\"\\\实现 X+1 图灵机\");

printf(\"\\n请输入 x (用2进制表示)：\"); scanf(\"%s\

strcpy(str,\"*0\");//这里是开始将*0放进str中，0是为了保存进位，初始化图灵机数据带

n=strlen(x);//获取x的长度

init(n,str);//调用初始化函数，对图灵机进行初始化

n=strlen(str)-2;

start(n);

show_x(str,x);

return 0;

}

四、执行结果

五、心得体会

形式语言与自动机学习完之后设计了一份关于图灵机的作业，但是那个时候是设计，没有使用代码实现，在实现的过程才发现，理论设计在设计到数据访问和保存的时候需要一些改进，因为在设计的时候并没有转换成代码实现，当实现的时候就需要了抽象思维，将设计的模型转换成可以实现的模型。我越来越发现计算机思维的重要性。