課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰項潔
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰2013/11/12
考試時限（分鐘）：180 min
是否需發放獎勵金：yes
（如未明確表示，則不予發放）
試題 :
其中Ξ是屬於的意思
1 (15pts) In each of the questions below determine whether the binary relation
P is reflexive, symmetric and/or transitive
1.1 The relation P on {1, 2, 3,...} where aPb means a divides b.
1.2 The relation P on the set of all people where aPb means a is younger
than b
1.3 The relation P on the set of all integers where aPb means a≠b
2 (20pts) We call a grammar regular if every rule is of the form
A → aB, A → a, or S → ε
Show that a language L is regular if and only if there is a regular
grammar G such that L = L(G)
3 3.1 Show that the set of context-free languages is closed under union,
concatenation, and Kleene star. (10pts)
3.2 Show that it is not closed under intersection (10pts)
2.2 Show that it is not closed under complement (10pts)
4 (15pts) Give a CFG that generates the language {a^i b^j c^k: i = j or j = k,
i, j, k ≧ 0}
5 Show that
5.1 {0^k u 0^k : k≧1, u Ξ {0, 1}* } is regular (10pts)
5.2 {0^k 1u 0^k : k≧1, u Ξ {0, 1}* } is not regular (10pts)
※ 編輯: yet5438 來自: 140.112.16.137 (11/12 12:38)