以下是作业原题 详情见文档
《计算理论基础》上机实验 1
实验名称:NFA 对字符串的识别 实验目的:
- 理解有穷自动机的概念
- 掌握 NFA 的运行过程，了解状态的转换过程。
实验学时:2 学时 实验内容:
(1) 理解 NFA 的工作原理，设计合适的数据结构或类，来表示如上图所示 NFA， 要求设计尽量具有通用性。
(2) 设计某些字符串作为输入的测试用例，判断 NFA 能否正确接受或拒绝这些字符 串，给出识别结果。
(3) 对于此 NFA 接受的字符串，展示出状态转移的全过程。
《计算理论基础》上机实验 2
实验名称：构造下推自动机 实验目的：
- 理解下推自动机的概念
- 掌握下推自动机的运行过程，掌握状态转换过程中堆栈的使用。
实验学时：2 学时
实验内容： 令 = {a, b, c}，L = {w | w ∈ {a, b, c}*, #b(w) = #c(w)}，其中#z(w)是字符 z 在 w 中 出现的次数。 例如，字符串 x = baccabcbcb ∈ L，因为#b(x) = #c(x) = 4。 类似的，字符串 x = abcaba ∉ L，因为#b(x) = 2，而#c(x) = 1。 构造一个下推自动机能够识别语言 L，并通过若干测试用例，验证构造的 PDA 能 否正确接受或拒绝这些字符串。
《计算理论基础》上机实验 3
实验名称：构造图灵机 实验目的：
- 理解图灵机的概念
- 掌握图灵机的运行过程，了解格局的转换。
实验学时：2 学时
实验内容： 构造一个图灵机能够识别语言 L = {#n +m = k | n + m = k}，并通过若干测试用 例，验证构造的图灵机能否正确接受或拒绝这些字符串。可在程序中用任意特定字 符替代””符号。