課程名稱︰自動機與形式語言
課程性質︰資工系大三必修
課程教師︰項潔
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰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