课程名称︰自动机与形式语言
课程性质︰资工必修
课程教师︰陈伟松
开课学院：电资
开课系所︰资工
考试日期（年月日）︰2018/1/11
考试时限（分钟）：3 hours
试题 :
(1)[2 points] Consider the following automaton A over alphabet Σ = {a,b}
╔═╗──a─→┌─┐
→║q ║ │p │
╚═╝←─b──└─┘
↑│ │
││ │
││ │
││ │
a b a
││ │
││ │
│↓ ↓
┌─┐ ┌─┐___a,b_
│ │─b──→│ s│ │
└─┘ └─┘←──┘
(i)Is A deterministic or non-deterministic?
(ii)Is aaa accepted by A?
(iii)Is ababa accepted by A?
(i v)Is baabb accepted by A?
(2)[2 points] Consider the following grammer G = <Σ,V,R,S>, where Σ = {a,b},
V = {S,A,B}, S is the starting variable and R contains the following rules:
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
(i) Is abba∈L(G)?
(ii) Is baaba∈L(G)?
(iii) Is aaa∈L(G)?
(i v) Is bbba∈L(G)?
Give its derivation tree, if you think a word is in L(G).
(3)[2 points] Prove that the following language is undecidable.
L_∞ := {│M│| M accepts infinitely many words}
└ ┘
(4)[2 points] Prove that if L∈NP , then L^*∈NP.
(5)[2 points] Prove that the following problem CFL-Complement is undecidable.
┌──────────────────────────────────┐
│CFL-Complement │
├──────────────────────────────────┤
│Input : A CFG G = <Σ,V,R,S>. │
│ │
│Task : Output True, if Σ^* - L(G) is a CFL. Otherwise output False.│
└──────────────────────────────────┘
Hint : Recall that the run of a Turing machine M on an input w:
C_0├C_1├C_2├C_3 ‥‥‥
can be represented as a word:
w_0#w_1^R#w_2#w_3^R# ‥‥‥
where each w_i is the configuration C_i itself.Each w_i^R denotes the reversal
of the string w_i.
First prove that there is a CFG G that generates all word that are not
aceepting run of M. Then, obtain a reduction from L_∞. Without proving it,you
may use the fact that if M accepts infinitely many words, the set of words
that are its accepting run is not CFL.