[試題] 104上 項潔 自動機與形式語言 期末考
課程名稱︰自動機與形式語言
課程性質︰資工系大三必修
課程教師︰項潔
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰2016/01/12
考試時限（分鐘）：170
試題 :
Problem 1 (20 points)
For each of the classes of languages Regular, Context-Free, Decidable, and
Turing-Recognizable, state whether they are closed under union, concatenation,
Kleene star, intersection, and complement. For each negative answer, explain
why.
Problem 2 (15 points)
Let A = {〈R, S〉| R and S are regular expressions and L(R) ⊆ L(S)}. Show that
A is decidable.
Problem 3 (15 points)
If A ≦ B and B is a regular language, does that imply that A is a regular
m
language? Why or why not?
Problem 4 (15 points)
_
Give an example of an undecidable language B, where B ≦ B.
m
Problem 5 (15 points)
Prove that there exists an undecidable subset of {1}*.
Problem 6 (15 points)
A grammar G = {V, Σ, R, S} is regular if every rule in R is of the form
A → aB or A → ε
Show that a language L is regular iff it can be generated by a regular grammar.
Problem 7 (15 points)
Show that a language L is decidable iff there is an enumerator E that enumerates
the members of L in non-decreasing order. (That is, if E prints out u , u , u ,
1 2 3
u , ..., then |u | ≦ |u | if i ≦ j.)
4 i j
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.212.7
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1452579595.A.580.html
※ 編輯: xavier13540 (140.112.212.7), 01/12/2016 14:20:39
推
01/12 14:33, , 1F
01/12 14:33, 1F
推
01/12 18:52, , 2F
01/12 18:52, 2F