課程名稱︰ 自動機與形式語言
課程性質︰ 資工系必修
課程教師︰ 林智仁
開課學院： 電機資訊學院
開課系所︰ 資訊工程學系
考試日期（年月日）︰ 2008/12/4
考試時限（分鐘）： 90
是否需發放獎勵金： 是
（如未明確表示，則不予發放）
試題 :
1.(a) (12%)
In using the pumping lemma, we use a property that
not(A and B and C) (1)
is equivalent to
B and C → not A, (2)
where A, B, and C are any statements.
Use a (detailed) truth table to prove the above property (i.e., prove (1)
is equivalent to (2). Please consider all 8 combinations of A, B, C;
don't put "B and C" as a variable).
(b) (13%)
In almost all Pumping Lemma examples we discussed, we consider
i
● A: xy z belongs to the language, for all i >= 0.
● B:│y│> 0
● C:│xy│=< p
and prove (2). Then from the above property that (1) and (2) are
equivalent, we obtain the desired result (1). Assume that instead of (2)
, we are now able to prove that
B → not A. (3)
Is (3) then sufficient to imply (1)? If your answer is yes, show your
argument and give an example (i.e., give a language and in the use of
pumping lemma you use (3)).
If your answer is no, give your detailed argument.
2.(20%)
Using pumping lemma to prove that the following language is not regular:
r s
{0 1 │ r >= 2s, r >= 0, s >= 0, r and s are integers}.
We required you to directly use the standard pumping lemma. Don't use
something else (eg. do complement of this language or union it with
something else; and then prove blah blah).
3.(25%)
Consider the following PDA with Σ = {0}:
┌─┐ 0,ε → 0 ┌─┐ 0,ε → ε ╔═╗
→│q0│ ─────→│q1│ ─────→ ║q2║
└─┘ └─┘ ╚═╝
Find CFG of this PDA's language. You are required to follow the same
procedure in Lemma 2.27 to generate rules (Lemma 2.27 proves that if a
PDA recognizes some language, then it is context free. Your notes should
have provided enough materials regardless of whether you have the
textbook or not.)
4.(20%)
Assume Σ={0, 1}. We would like to design a (one-tape deterministic)
Truing machine to shift a string. That is, if w is the input, after
running the machine, we have Uw in the tape. Give the transition diagram
as well as the formal definition of this TM.
5.(10%)
Consider the following two-tape TM:
U → R U → L 0 → R U → R
┌─┐ U → R ┌─┐ U → L ┌─┐ U → R ┌─┐ U → R ┌─┐
→│q0│ ────→│q1│────→│q2│────→│q4│ ────→│qa│
└─┘ └─┘ └─┘ └─┘ └─┘
0 → R │↑ ↑│ │↑U → 0,R
U → 0,R││ ││ ││0 → R
└┘ U → L ││0 → R └┘
0 → L ││0 → L
││
│↓
┌─┐
│q3│
└─┘
Assume the initial configuration is U0000 in the first tape and UU... in
the second tape. Run the TM and give the sequence of configurations.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.229.226.87