问题

问题5.1：为5.1.1节中语法C的最右侧派生中，句子形式的开放部分构建一个正则语法。

问题5.2：图Fig5.7和Fig5.12的FS自动机只有一个可接受状态，但是图Fig5.15（c）中的自动机有多个可接受状态。那多重可接受状态是否是必要的？注意：1.是否任何FS自动机A都能转换为只有一个可接受状态的FS自动机B？2.此外B是否不具有ε转换？3.B是否是确定性的？

问题5.3：展示在清理正则语法时，可以按照任意顺序执行删除非生成性规则和不可到达的非终结符的语法清理操作。

问题5.4：设计一种算法，可以从一个FS自动机中删除ε转换。

问题5.5：设计一种方法，在正则语法而不是自动机上执行正则自动机（5.5节）的完成和逆向。

问题5.6：对于有逻辑背景的读者：对FSA的补充进行二次补充，并不一定会产生原始自动机，但是对已经进行过补充的补全FSA的补全会产出一个原始自动机，这表明补全自动机在某种程度上是不同的。分析这种现象，并找到与直觉逻辑相似的地方。

问题5.7：项目：研究FSA的分解/裂解；例如Roche [148]。

问题5.8：当我们为每个非终结符A分配两个状态时，A_s表示“A开始”，A_f表示“A完成”，那么规则A → XY会带来3个ε转换，$$A_s\stackrel{\epsilon }{\to }{X}_s$$，$$X_f\stackrel{\epsilon }{\to }{Y}_s$$和$$Y_f\stackrel{\epsilon }{\to }{A}_f$$，以及一个非ε转换$$X_s\stackrel{X}{\to }{X}_f$$或者$$Y_s\stackrel{Y}{\to }{Y}_f$$，这取决于X或Y谁是终结符。用这个视图，写出比5.6节更对称且结合更好的左正则和右正则语法。

问题5.9：从Earley解析器（7.2节）生成一个子集算法，可以在左正则语法上起作用的。

问题5.10：从图Fig5.22的语法生成一个正则表达式。

问题5.11：项目：5.7节演示了如果通过初始化假设所有非终结符都相等来最小化一个FS自动机/语法。那么CF语法是不是也有类似的过程呢，又能得到什么呢？

问题5.12：历史：追溯Kleene star的使用起源，升起的星星的意思是“一组无界事件集”。（见[135]）