[試題] 106-1 陳偉松 自動機與形式語言 期末考
課程名稱︰自動機與形式語言
課程性質︰資工必修
課程教師︰陳偉松
開課學院：電資
開課系所︰資工
考試日期（年月日）︰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.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.252.205.53
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1518009004.A.89A.html
※ 編輯: ppappeoh (111.252.205.53), 02/07/2018 21:11:23
推
02/07 23:48,
6年前
, 1F
02/07 23:48, 1F