发信人: Tux (可怜，我的2008), 信区: e_note
标  题: Re: [形式语言与自动机]2009.1.14考题（B卷）
发信站: 酒井BBS (Wed Jan 14 16:30:27 2009), 转信

附加题（原题用英文表述）：

A1：

给定任意一个接受的串长度为偶数的DFA，构造PDA，此PDA接受的串跟上边所述DFA的
串数量相同并且成如下关系：
假设DFA接受的某个串为 x_1 x_2 x_3 x_4 …… x_{2n-1} x_{2n}，
那么PDA接受的对应的串为 x_2 x_1 x_4 x_3 …… x_{2n} x_{2n-1}

A2：
       *          *
证明 S===>w iff S===>w
                 lm

【 在 chokkyvista (刚嗨嗨) 的大作中提到: 】
: 标  题: [形式语言与自动机]2009.1.14考题（B卷）
: 发信站: 酒井BBS (Wed Jan 14 15:42:34 2009), 转信
: 
: 一.判断题
:     1.任一空栈接收的PDA，存在一个终态接收的PDA与之等价。
:     2.任一无二义性的CFG，存在一个DPDA接收该CFG生成的CFL。
:     3.任意一个P问题都是NP的。
:     4.任一递归可枚举语言(RE)，存在一个停机的TM接收它。
:     5.在同一个字符集\Sigma下，空语言的Klein闭包不等于{\epsilon}的Klein闭包（即\emptyset^{*} != {\epsilon}^{*}）。
:     6.L1是正则语言，L2不是正则语言，则L1与L2的并不是正则语言。
:     7.存在一个算法，判定两个正则表达式生成的语言是否相等。
:     8.任一半无限长(semi-infinite)带的TM，存在一个双栈PDA与之等价。
: 
: 二.单选，从A~H中选一个与1~6匹配
:     1.L(a^{*}b^{*})
:     2.{a^nb^n | n>0}
:     3.{a^nb^m | n>m>0}
:     4.{ww | w \in {a,b}^{*}}
:     5.{ww^R | w \in {a,b}^{*}}
:     6.L_u (i.e. {(M,w) | w \in L(M)})
: 
:     A.能被DFA接收 且 能被空栈接收的DPDA接收
:     B.能被DFA接收 且 不能被任何空栈接收的DPDA接收
:     C.能被终态接收或空栈接收的DPDA接收 且 不能被任何DFA接收
:     D.能被终态接收的DPDA接收 且 不能被任何空栈接收的DPDA或DFA接收
:     E.能被PDA接收 且 不能被任何DPDA接收
:     F.能被停机的TM接收 且 不能被任何PDA接收
:     G.能被TM接收 且 不能被任何停机的TM接收
:     H.不能被任何TM接收
: 
: 三.简答
:     1. S -> AB
:        A -> aAb | \epsilon
:        B -> cB | \epsilon
:     (1) 消去所有epsilon产生式
:     (2) 在上一题的基础上消去所有unit产生式
:     (3) 在上一题的基础上将文法转成CNF(Chormsky Normal Form)
: 
:     2. S -> DE | DC | CA | a
:        A -> DE | DC
:        B -> CA | DE | DC | a
:        E -> BC
:        C -> a
:        D -> b
:     (1) 在串baa上使用CYK算法，给出X_{ij} (1<=i<=j<=3)
:     (2) 判断baa是否属于G[S]生成的语言
: 
:     3. S -> aSbS | aS | c
:     (1) 说明G[S]是二义文法
:     (2) 给出接收G[S]生成语言的空栈接收的PDA
: 
:     4. 给出判定如下问题的算法描述：
:     (1) 给定CFG G，判断L(G)是否为空语言
:     (2) 给定CFG G，判断\epsilon是否属于L(G)
: 
:     5. 给出了一个DFA A（原题用状态图给出）：
:       ________|__a__|__b__|__
:       -->*q_0 | q_1 | q_2 |
:          *q_1 | q_1 | q_0 |
:           q_2 | q_1 | q_2 |
:     (1) 构造一个DFA 接收 ({a,b}^{*}-L(A))^R
:     (2) 定义同态映射h: h(0)=ba, h(1)=ab，构造一个DFA 接收 h^{-1}(L(A))
: 
:     6. 给出 PDA P = (Q_p, \Sigma, \Gamma, \delta_p, q^p_0, Z_0, F_p) 
:          和 DFA D = (Q_d, \Sigma, \delta_d, q^d_0, F_d)
:        设其分别接收语言L1，L2，要求构造一个PDA P^{'} 使其接收 L1交L2，给出P^{'}的转移规则\delta即可
:        （假设 P^{'} = (Q_p*Q_d, \Sigma, \Gamma, \delta, (q^p_0,q^d_0), Z_0, F_p*F_d)，其中*为笛卡尔积）
: 
: 四.构造题
:     1. 构造一个DFA，要求|Q|<=8，使其接收语言
:        L={w | w \in {0,1}^{*}, w包含00子串但不含000子串}
: 
:     2. 写出正则表达式E，要求运算符个数不超过8（括号不算），使其产生语言
:        L={w | w \in {a,b}^{*}, w不含aa子串}
: 
:     3. 构造一个CFG，要求产生式数目不超过8，使其产生语言
:        L={a^nb^mc^k | n<=m+k, n>=k, m,n,k>=0}
: 
:     4. 构造PDA，空栈接收或终态接收皆可，使其接收语言
:        L={w | w \in {a,b,c}^{*}, w中a,b个数相等}
: 
:     5. 构造TM，要求|Q|<=5，使其接收语言
:        L={w | w \in {a,b}^{*}, w中a,b个数都是偶数}
: 
: 五.证明题
:     1. G[S]: S -> aSbb | aSbbb | \epsilon
:        求证：L(G) = {a^nb^m | 2n<=m<=3n, n,m>=0}
: 
:     2. 证明 L={w | w \in {a,b,c,d}^{*}, w中a,b,c个数相等且a,b,c互不相邻} 不是CFL
: 
:     3. 证明子集构造算法的正确性
: 
: --
: 
※ 修改:·Tux 于 Jan 15 10:31:17 2009 修改本文·[FROM: 211.99.150.242]
: ※ 来源:·酒井BBS bbs.net9.org·[FROM: 59.66.141.148]


--
酒井四大牛：
 封sail手动
 弹黑手唧唧
 放梦幻鸽子
 去Female偷窥
        ——你，能做几样？


※ 来源:·酒井BBS bbs.net9.org·[FROM: 211.99.150.242]