计算理论模拟试题

计算理论模拟试题

《计算理论》复习题

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

*

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库计算理论模拟试题在线全文阅读。