计算理论模拟试题

计算理论模拟试题

《计算理论》复习题

1、设语言A=｛w | w含有子串0101，即对某个x和y，w=x0101y｝，字母表为{0，1} a. 画出识别A的DFA的状态图。

b. 画出识别A的NFA的状态图（规定状态数为5）。

解: a．

b．

2、把下图的有穷自动机转换成正则表达式。

解: 1、加新的开始状态和新的结束状态

2、删除状态1，通过状态1的转换有s→1→2、2→1→2

3、删除状态2

*