清华大学本科生考试试题专用纸 考试课程 《形式语言与自动机》 A卷 2003年 7 月 2 日 学号: 姓名: 1. (34 pts) 回答 true 或者 false ( Answer true or false ): (2 pts. each) a) _____ 如果一个语言是正规的,那么它可由某个右线性文法生成(If a language is regular, it can be generated by a right-linear grammar). b) _____ 对于每一个可以被非确定 PDA 接受语言,都存在一个接受它的确定的 PDA (For every language accepted by a nondeterministic PDA, there is a deterministic PDA that accepts the same language). c) ______ 每个二义文法可以转化为等价的无二义文法(Every ambiguous grammar can be converted to an equivalent unambiguous grammar). d) ______ 所有C++程序的集合是一个形式语言(The set of all possible C++ programs is a formal language). e) ______ 由以下产生式定义的文法符合 Chomsky 范式的形式(The following grammar is in Chomsky Normal Form). S ? AB A ? aA | a B ? bB | b f) _______ 针对正规语言的 pumping 引理可用于证明一个语言是正规的(The pumping lemma for regular languages can be used to prove that a language is regular). g) _______ 语言 L= { wwR?w? {a, b}* }是正规的,其中 wR 代表 w 的反向字符串(下同)(The language L= { wwR?w ? {a, b}* } is regular,where wR is the reversal of w ( the same in the rest part below )). h) _______ 对一个 DFA 应用填表算法,合并所有不可区分的状态,则可获得一个等价于该 DFA 的拥有“最少”状态数目的DFA(After applying the table-filling algorithm to a DFA and combining all the distinguished states, one can get an equivalent DFA with the least state number). i) _______ 对每个可以被 DPDA 接受的语言,都存在一个无二义的上下文无关文法接受它(Every language accepted by a DPDA has an unambiguous context-free grammar). j) _______ 递归语言不是递归可枚举语言(A recursive language is not a recursively enumerable language). k) _______ 一个语言可被带三个栈的 PDA 接受,则它也可以由带两个栈的 PDA 接受(Every language accepted by a PDA with three stacks can also be accepted by a PDA with two stacks). l) _______ 一个语言可被带两个计数器的计数器机接受,则它也可由带一个计数器的计数器机接受(Every language accepted by a two-counter machine is also accepted by a one-counter machine). m) _______ 对任何语言 L1 和 L2,如果 L1 不是正规的,且 L1 ? L2,那么 L2 不是正规的(For any languages L1, L2, if L1 is not regular and L1 ? L2,then L2 is not regular). n) _______ 对任何语言 L1 和 L2,如果 L1 和 L2 不是正规的,那么 L1 ? L2 不是正规的 (For any languages L1, L2, if L1 and L2 are not regular, then L1 ? L2 is not regular). o) _______ 对任何正规语言 L1和L2,L1 ? L2 L1 = (L1 ? L2) L1(For any regular languages L1 and L2, L1 ? L2 L1 = (L1 ? L2) L1). p) _______ 对任何上下文无关语言 L1和L2,L1 ? L2 也是上下文无关的(For any context-free languages L1 and L2, L1 ? L2 is context-free). q) _______ 终态方式接受的PDA所接受的语言,一定可以被空栈接受方式的PDA所接受;类似地,终态方式接受的DPDA所接受的语言,一定可以被空栈接受方式的DPDA所接受.(A language accepted by final state by a PDA is accepted by empty stack by a PDA. Similarly, a language accepted by final state by a DPDA is accepted by empty stack by a DPDA). 2. (12 pts) 考虑正规表达式r = a*b(a + b)(Consider the regular expression r = a*b(a + b)). a) 构造一个接受L(r) 的?-NFA(Construct a ?-NFA that accepts L(r)). (3 pts) b) 给出语言L(r) 的反向的一个正规表达式(Give a regular expression for the reversal of L(r)). (3 pts) c) 构造可以生成语言 L(r) 的一个上下文无关文法(Construct a context-free grammar generating the language L(r)). (6 pts) 3. (6 pts) 下图是一个扩展的两个状态的有限自动机,其中 R,S,T,和 U 是正规表达式。可以用不同的形式给出等价于该扩展自动机的正规表达式,试给出两种这样的正规表达式。(Give two regular expressions which describe the following generic two-state finite automata in two different ways, where R, S, T, and U are regular expressions.) RSStartTU 4. (6 pts) 正规表达式 a*b 表示 {a, b} 上的一个语言。试构造接受该语言的补语言的一个 DFA。(The regular expression a*b denotes a language on {a, b}. Construct a DFA that accepts the complement of this language.) 5. (8 pts) 试给出下列每个正规语言的一个正规表达式(Give a regular expression for each of the following regular languages): a) { xwxR ? x, w ? (a + b)+ }, where (a + b)+ = (a + b) (a + b)* w : w 2 fa; bg **Rb) { w?w ? {a , b} ? ?x, y( x, y ?{a , b} ? w = xy ? | y | =3 ? y = y ) } 6. (7 pts) 下面是图灵机 M 的转移图。对于输入字符串00122,给出 M 从初始 ID 开始可以到达的所有可能的 ID (Following is a transition diagram for Turing machine M. Show all of the ID’s reachable from the initial ID if the input is 00122). Y / Y0 / 0Start0 / X1 / YZ / Z1 / 12 / ZZ / Z1 / 1Y / Y0 / 0q0q1q2q3Y / Yq4Z / Zq5X / XB / Bq6Y / YZ / Z7. (8 pts) 考虑由下列产生式定义的上下文无关文法 G(Consider the context-free grammar G defined by productions): S? 0S1 ? ?. 证明L(G)={ 0n1n ? n?0}(Prove that L(G)={ 0n1n ? n?0}). 8. (8 pts) 下列文法可产生所有正常嵌套的括号串,所有正常嵌套的括号串构成一个语言。试构造一个接受该语言的空栈接受方式的下推自动机(6 points),然后再将其转换为等价的终态接受方式的下推自动机(2 points)(The following grammar generates all strings of properly nested parentheses. Construct a pushdown automaton that accepts this language by empty stack and then convert it to an equivalent PDA which accepts the same language by final sate). S?(S)? SS ? ?. 9. (5 pts) 下列文法可产生所有正常嵌套的括号串。试消去该文法中的 ?-产生式,使得到的新文法可以产生除空串之外的所有正常嵌套的括号串(The following grammar generates all strings of properly nested parentheses. Eliminate the ?-productions to form a grammar generating the nested parentheses without empty string). S?(S)S ? ?. 10. (6 pts) 应用针对上下文无关语言的 pumping 引理,说明语言 L = {akbkak| k?0}不是上下文无关的 (Use the pumping lemma for context-free languages to show the language L = {akbkak| k?0} is not context free). 第 页/共 3 页
形式语言与自动机试题(A卷)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)