作者kevin1ptt (蚁姨椅yee)
看板NTU-Exam
标题[试题] 105-1 陈伟松 自动机与形式语言 期末考
时间Fri Jan 13 11:41:39 2017
课程名称︰自动机与形式语言
课程性质︰大三上必修
课程教师︰陈伟松 (Tony Tan)
开课学院：电资
开课系所︰资讯工程学系
考试日期（年月日）︰106/1/10
考试时限（分钟）：180
试题 :
In the following all the languages are over the alphabet Σ = {0, 1}.
(1) Consider the following automaton A.
http://i.imgur.com/qfvay5X.png
(i) [2 points] Is A deterministic or non-deterministic?
(ii) [2 points] Is 1010001 accepted by A? Is 0001110 accepted by A?
(iii) [2 points] Is there a word of length 7 that is accepted by A?
If there is, give one.
(iv) [2 points] What is the regular expression for L(A)?
Hint: Consider its complement.
(2) Consider the following CFG G with the following rules,
where S is the starting variable:
S → 0S1 | 1S0 | ɛ
(i) [2 points] Is 10110 generated by G? Is 1010 generated by G?
(ii) [2 points] Is there a word of length 8 that is generated by G?
If there is, give one.
(iii) [2 points] Is there a word of length 13 that is generated by G?
If there is, give one.
(iv) [2 points] Prove that the language L(G) is not regular.
(3) [4 points] Consider the following language:
L := { M | M is a Turing machine that accepts the string 101 }
└ ┘
Prove that L is undecidable.
(4) [5 points] Recall the definition of the problem SAT.
┌───────────────────────┐
│ SAT │
├───────────────────────┤
│ Input: A propositional formula φ in CNF. │
│ Task: Output True, if φ is satisfiable. │
│ Otherwise, output False. │
└───────────────────────┘
We know that SAT is NP-complete. Recall also the 3-color problem.﹡
┌───────────────────────┐
│ 3-color │
├───────────────────────┤
│ Input: A (undirected) graph G = (V, E). │
│ Task: Output True, if G is 3-colorable. │
│ Otherwise, output False. │
└───────────────────────┘
We have proved that 3-color is NP-complete by reducing SAT to 3-color.
Is there a polynomial-time reduction from 3-color to SAT?
If there is, give one such reduction.
──────────────────
﹡ A graph G is 3-colorable, say by R, G, B (Red, Green, Blue),
if we can color the vertices with R, G, B such that for every edge
(u, v) in G, the vertices u and v have different colors.
Here one vertex must have exactly one color.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 58.114.180.11
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1484278904.A.540.html
※ 编辑: kevin1ptt (58.114.180.11), 01/13/2017 11:44:09
1F：推 Gin1024 : 推 Tony 的弟子 01/15 01:16