计算理论----
型
一、证明一个语言是非正则语言。
思路:利用----泵定理(一)设 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:考工作过程、格局转换,不考设计机器