清华大学本科生考试试题专用纸 考试课程 《形式语言与自动机》 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卷)
