[試題] 100上 項潔 自動機與形式語言 期中考
課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰項潔
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰2011/11/22
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
^n 表示上標，_n 表示下標，￡ 表示屬於，Ε 表示包含於
1.
Let L Ε {0, 1}* be the language of all the strings that have equal number
of 0s and 1s.
(a) Give a three-state PDA for L.
(b) Give a CFG for L.
2.
Show that the class of context-free languages is closed under
union, concatenation, and Kleene star.
3.
Let A = {0^m 1^n 2^n: m, n ≧ 0} and B = {0^m 1^m 2^n: m, n ≧ 0}.
(a) Show that A and B are both context free.
(b) Show that the class of context-free languages is not closed under
intersection.
4.
Let A = {0^p: p is a prime}.
(a) Show that A is not regular.
(b) Show that A* is regular.
5.
We define the quotient of languages L_1 and L_2, denoted as L_1/L_2,
to be {w: wx ￡ L_1 for some x ￡ L_2}. Show that the class
of regular languages is closed under the quotient operation.
6.
Let L Ε {0, 1}* be a regular language, and let A Ε {0, 1}*
be a language in which, for each w ￡ A, there exists x ￡ L such that
(i) |w| = |x| (ii) w and x differ in at most one symbol position.
Show that A is regular.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.117.176.59
※ 編輯: paul112004 來自: 59.117.176.59 (11/22 20:57)
※ 編輯: paul112004 來自: 59.117.176.59 (11/22 20:57)
→
11/23 01:24, , 1F
11/23 01:24, 1F