计算理论考试

计算理论----考型 一、一个语言是非正则语言。 思路：利用----泵定理（一）设 L是一个正则语言，则存在正整数 1n ³ 使得任一字符串w L∈ 只要 w n³ 就可以写成w xyz= ，其中 ,y e xy n梗 且对每一个 0, ii xy z L澄 。 过程：假设给定的语言是正则语言，可以写成w xyz= （ y e¹ ），则 xz L∈ 。证明与上述 定理是矛盾的。（P55） 二、给定语言，写出 RE，设计 FA（形式化定义，状态图） 例：设计一台接受语言 ( ) { ( , )*, 3 }L w w a b w b=� 不包含 个连续的 的 DFA。 0 1 2 3 0 0 1 2( , , , , ), { , , , }, { , }, , { , , }M k s F k q q q q a b s q F q q qδ= Σ = Σ = = = ,状态转换用表格 表示如下 q σ δ(q,a) q0 a q0 … … … 考虑： ( ) { ( , )*, 3 }L w w a b w b= ∈ 包含 个连续的 三、构造一台接受给定语言的 DFA。 解题思路同二。 四、给定 NFA，构造 DFA。 解题思路，先写出起始状态，然后根据所输入的字符写出能够到达的所有状态。 五、给定 FA，构造 RE。 例： 解答： 计算理论----考试题型 *a b *a ba b * * *( )a b a ba b 六、状态最小化。 先将所有状态归为 A（终结），B（非终结），根据输入进行状态分解，直到不能再分。 七、证明 L是非上下文无关语言。 思路：利用泵定理（二）设 ( ), , ,G V R S= S 是一个上下文无关文法。那么 ( )L G 中任一长 度大于 ( )VGφ − Σ 的字符串 w 可以写成 w uvxyz= 使得 v 或 y 不是空串，并且对每一个 0,n ≥ ( )n nuv xy z L G∈ 。 八、设计 PDA，能识别给定语言。 例： ( , , , ), { | | , }G V R S R S aAa bAb e A SSΣ = → → ，构造一台 PDA，识别上面文法定义 的语言。 九、给定语言，构造 CFG，L（G）。*** 十、描述机器 TM功能，写出格局转换。 十一、 多带机：工作过程，格局转换。 TM：考工作过程、格局转换，不考设计机器