FLA Project 报告

一、分析与设计思路

1、解析器

解析器较为简单，只需根据命令行的参数打开对应的tm文件，然后将对应的状态集、输入符号集、纸带符号集、初始状态、空格符号、终结状态集、纸带数、转移函数进行解析并存贮到一定的数据结构中，比如状态集、输入符号集等就是用hash表存贮（unordered_set），转移函数使用unordered_map存贮，其中key值为"旧状态 旧符号组"，value值为"新符号组 方向组 新状态"。对于tm文件中的一些常见的语法错误进行适当的报错即可。

2、模拟器

模拟器也不难，首先检查输入的字符串是否在输入字符集中，如果不在直接报错，在verbose模式下找出第一个非法字符并指出即可。

设计vector<int>leftmost, rightmost, curidx，分别记录每一条纸带上最左边、最右边需要打印的字符位置以及当前指针指向的字符位置。接下来就根据当前状态和指向的符号组寻找转移函数，根据转移函数更新状态以及指针的位置。其中leftmost和curidx数组初始值全为 \(0\)，rightmost[0] = max(0, (int)input.size()-1)，其中input为输入的字符串，rightmost数组的其他位置初始值也为 \(0\).

leftmost更新方法如下：若转移函数中第i个纸带指针位置保持不变（即为*），则不更新；若向左移动（即为l），则leftmost[i] = min(leftmost[i], curidx[i])；若向右移动（即为r），若转移函数中新符号组第i个是空格符号B（即将原来的位置变为空格）且旧指针指向的位置就是leftmost[i]，则将leftmost[i]++。

至于rightmost的更新方法，和leftmost类似，代码如下：

if(direction[i] == 'l')
{
    --curidx[i];
    leftmost[i] = min(leftmost[i], curidx[i]);
    if(ng[i] == B && rightmost[i] == curidx[i]+1)
        rightmost[i]--;
}
else if(direction[i] == 'r')
{
    ++curidx[i];
    rightmost[i] = max(rightmost[i], curidx[i]);
    if(ng[i] == B && leftmost[i] == curidx[i]-1)
        leftmost[i]++;
}

在verbose模式下打印当前状态，对于每条纸带，只需打印下标在leftmost和rightmost数组之间的字符即可。

对于最后的打印结果，去除掉第一条纸带上下标leftmost[0]和rightmost[0]之间两边的空格字符，打印中间的非空格字符即可，代码如下：

int left = leftmost[0], right = rightmost[0];
while(left <= right && tapes[0][left+diff] == '_')
    left++;
while(right >= left && tapes[0][right+diff] == '_')
    right--;
if(!verbose)
{
    for(int i=left; i<=right; i++)
        cout<<tapes[0][i+diff];
    cout<<endl;
}
else
{
    cout<<"Result: ";
    for(int i=left; i<=right; i++)
    {
        cout<<tapes[0][i+diff];
    }
    cout<<"\n==================== END ====================\n";
}

3、图灵机程序

1. 实现二进制数的循环右移操作，这个只需用到一条纸带即可，若为空串，直接停机；其余情况先将纸带上的字符统一向右移动一位，再将最后一个字符移动到开头的位置（课件上有转移图，不详细叙述了）。

2. 第二个图灵程序，思路如下：首先，若字符串为空串，则直接在第一条纸带上打印true。
   若不为空串，注意到任意一个非零平方数都可以表示成

   \[\sum\limits_{i=1}^n{(2i-1)}\ (n\in N) \]

   的形式。这样我们只需先在第一条纸带上向右走1步，再走3步，再走5步，以此类推。若在某一轮恰好能走完，则打印true；若在某轮中途就走完，则打印false；没走完则在第二条纸带后面再添加两个 \(1\)，再开始新一轮的比较。
   总结一下，第一条纸带上指针只需不回头的向右走并不断将前面的字符清空，第二条纸带负责表示 \(1,3,5,7\cdots\) 个字符 \(1\)，并不断与第一条纸带上剩下的字符串进行比较直到第一条纸带上字符完全清空。最后根据是否在某一轮恰好走完确定输入字符串长度是否为平方数。

二、实验完成度

本次实验所有的必做部分皆已完成。

三、实验中遇到的问题

本次实验比较简单，基本上两三天就完成了，所以没有遇到太多的问题。

四、总结感想

本次实验让我比较直观地去感受图灵机的运行过程，通过动手实践更好地去理解了图灵机的一些理论，还是有一定的收获的。

五、对课程和实验的意见与建议

我上这门课主要是觉得卜磊老师讲的理论很有趣，能够锻炼自己的逻辑思维。对于实验，我感觉还是比较简单，建议可以在明年加大难度。