25-26-2-理论计算机科学基础-期中

1、2.（题面暂缺）

第 1、2 题题面暂缺，当前仅保留考点回忆：给出了文法的生成式，进行文法类型判断、由右线性文法导出正则表达式等。
即当出现形如 $x=\alpha x+\beta$ 的方程时，可用 Arden 引理写为 $x=\alpha^{*}\beta$ 。

已知右线性文法 G, 请构造相应的有限自动机。

G=(\{S, A, B\}, \{a,b\}, P,S)

生成式 $P$ 如下:

\begin{aligned} S &\to aA \mid baB \mid a \\ A &\to aA \mid aS \mid bB \\ B &\to bB \mid b \mid a \end{aligned}

答案 / 解析

产生式集合 $P$ 经过拆分标准化后如下：

\begin{aligned} S &\to aA \mid bC \mid a \\ C &\to aB \\ A &\to aA \mid aS \mid bB \\ B &\to bB \mid b \mid a \end{aligned}

根据上述产生式，我们可以构造一个非确定有限自动机 (NFA)：

考点为：含 $\varepsilon$ 转换的 NFA、无 $\varepsilon$ 转换的 NFA 与 DFA 三者之间的等价转换。

写出第5题题图中有限自动机接收的字符串集合。

使用泵浦引理证明集合 $\{ a^n b^m c^{n+m} \mid n, m \geq 1 \}$ 不是正则集。

题图缺，考查内容为：填表法化简DFA M，求出最简自动机。

构造最简的DFA M能够产生下列语言。终止符号的集合为 $\{a, b\}$ 。

答案 / 解析

答案 / 解析