发信人: Yaksa (是涮羊肉不是麻辣烫), 信区: e_note
标  题: 形式语言与自动机2003
发信站: 酒井BBS (Sat Dec 20 16:16:39 2003), 转信


图都没画。

清华大学本科生考试试题专用纸考试课程  
《形式语言与自动机》 B卷     2003年 7 月 2 日
学号：                 姓名：               

1. (34 pts) 回答 true 或者 false ( Answer true or false ):  (2 pts. each)

a) _____ 如果一个语言可由某个右线性文法生成，那么它是正规的 （If a language can be generated by a right-linear grammar, it is regular） .

b) _____ 对于每一个可以被确定 PDA 接受语言，都存在一个接受它的非确定的 PDA （For every language accepted by a deterministic PDA, there is a nondeterministic 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 gram
mar is in Chomsky Normal Form）. S -> AB     
                                 A ->AA | a
                                 B ->BB | b
f) _______ 针对正规语言的 pumping 引理不可用于证明一个语言是正规的（The pumping lemma for regular languages can't 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 not regular，where wR is the revers
al 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）.
注：此题选择False

i) _______ 对每个可以被 DPDA 接受的语言，都存在一个无二义的上下文无关文法接受它（Every language accepted by a DPDA has an unambiguous context-free grammar）.

j) _______ 递归语言是递归可枚举语言（A recursive language is a recursively enumerable language）.

k) _______ 一个语言可被带三个栈的 PDA 接受，但它不可以由任何带两个栈的 PDA 接受（Every language accepted by a PDA with three stacks can't be accepted by any 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 U L2 是正规的（For any languages L1, L2, if L1 is regular, then L1 U L2 is 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 U L2 L1 =L1 (L1 U L2)（For any regular languages L1 and L2,  L1 U L2 L1 = L1 (L1 U L2)）.

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. Si
milarly, a language accepted by final state by a DPDA is accepted by empty s
tack by a DPDA）.

2. (12 pts) 考虑正规表达式r = b(a + b)a*（Consider the regular expression r = b(a + b)a*）.
a)     构造一个接受L(r) 的e-NFA（Construct a e-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.）.

4. (6 pts) 正规表达式 ab* 表示 {a, b} 上的一个语言。试构造接受该语言的补语言的
一个 DFA。（The regular expression ab* denotes a language on {a, b}. Constru
ct 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)*
b)  { w |w 属于 {a , b}* 且 存在x, y( x, y 属于{a , b}且 w = xy 且 | x | =3 且 x = xR ) }
               最后这个R是x的上标

6. (7 pts) 下面是图灵机 M 的转移图。对于输入字符串01122，给出 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 01122）.

7. (8 pts) 考虑由下列产生式定义的上下文无关文法 G（Consider the context-free 
grammar G defined by productions）：S->0S1 | e.   （e是那个表示空的希腊字符）
证明L(G)={ 0n1n | n大于等于0}   （ 0n,1n分别表示0，1的n次方）
（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 | e.   (e是那个表示空的希腊字符）

9. (5 pts) 下列文法可产生所有正常嵌套的括号串。试消去该文法中的 e-产生式，使得
到的新文法可以产生除空串之外的所有正常嵌套的括号串（The following grammar ge
nerates all strings of properly nested parentheses. Eliminate the e-producti
ons to form a grammar generating the nested parentheses without empty string
）.
S->（S）S | e.

10. (6 pts) 应用针对上下文无关语言的 pumping 引理，
说明语言L={akbk+1ak| k大于等于0}  （ak为a的k次方，bk+1为b的k+1次方）
不是上下文无关的 （Use the pumping lemma for context-free languages to show the language L = {akbk+1ak| k>=0} is not context free）.

--


   


   
            我听见风       来自地铁和人海  


※ 修改:·Yaksa 于 Dec 20 16:17:06 修改本文·[FROM:  219.224.140.70]
※ 修改:·Yaksa 于 Dec 20 16:23:01 修改本文·[FROM:  219.224.140.70]
※ 来源:·酒井BBS bbs.net9.org·[FROM: 219.224.140.70]