課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰林智仁
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2009.12.01
考試時限（分鐘）：
試題 :
˙ Please give details of your calculation. A direct answer without
explanation is not counted.
˙ Your answers must be in English.
˙ Please carefully read problem statements.
˙ During the exam you are not allowed to borrow others' class notes.
˙ Try to work on easier questions first.
Problem 1 (25%)
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
˙ A: x(y^i)z ∈ the language, ∀i ≧ 0
˙ B: |y| ＞ 0
˙ C: |xy| ≦ p
Recall that the first example in our lecture is for the language
n n
{ 0 1 │n ≧ 0 }.
In the proof, instead of using (2), we only use
B → not A. (3)
That is, we did not check if |xy| ≦ p. The reason is that (3) implies (2)
(or (3) implies (1)).
Question: Is it possible to have an example using only
C → not A (4)
for the proof? If your answer is yes, show your argument and give an example
(i.e., give a non-regular language and in the use of pumping lemma you use
(4)). If your answer is no, give your detailed argument.
Problem 2 (20%)
Consider the following PDA with Σ = {0, 1}:
┌─┐ε, ε→ $ ┌─┐─╮ 0, ε→ 0
start ─→│q1│─────→│q2│←╯ 1, ε→ 1
└─┘ └─┘
│
│ ε, ε→ε
↓
╔═╗ ┌─┐
║q4║←─────│q3│←╮ 0, 0 →ε
╚═╝ ε, $ →ε └─┘─╯ 1, 0 →ε
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.)
Problem 3 (15%)
╔═╗ε, ε→ $ ┌─┐─╮ 0, ε→ 0
start ─→║q1║─────→│q2│←╯ 1, ε→ 1
╚═╝ └─┘
│
│ ε, ε→ε
↓
╔═╗ ┌─┐─╮ 0, 0 →ε
║q4║←─────│q3│←╯ 1, 0 →ε
╚═╝ ε, $ →ε └─┘
Consider the above PDA. Draw the tree to process the string 0110. Your tree
must be complete. Note that we mean a tree to process an input string. We
don't mean a parse tree of CFG.
Problem 4 (20%)
Transform the following CFG to CNF. You need to show details of all steps.
Since S does not appear on the right-hand side for each rule, you do not need
to add an additional S_0 → S.
S → A | B
A → 0A1 | B | ε
B → 1B0 | A
PS. 題目原文是 S_1 和 S_2，為了方便觀看，我把 S_1 和 S_2 分別代換成 A 和 B
Problem 5 (20%)
˙ Construct a Turning machine (i.e., showing the state diagram) for the
language
(3^n)
{ 0 │ n ≧ 0 }
˙ Give its formal definition (including a table for δ).