課程名稱︰ 自動機與形式語言
課程性質︰ 必修
課程教師︰ 林智仁
開課學院： 電資學院
開課系所︰ 資訊工程
考試日期（年月日）︰ 2014/12/16
考試時限（分鐘）：
試題 :
‧ Please give details of your answer. 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 other's class notes.
‧ Try to work on easier question first.
Problem 1 (5 pts)
Consider the following DFA,
a
┌─┐────→╔═╗─┐b
start →│q1│←────║q2║←┘
└─┘ a ╚═╝
↑│ ↑
││ │
b ││b │a
││ ╔═╗ │
│└─→║q3║─┘
└───╚═╝
Give a CFG with ≦ 8 rules to describe the above language.
Problem 2 (10 pts)
Consider the following language,
i j k
{a b c │i = j or i = k, i ≧ 0, j ≧ 0, k ≧ 0}
Give a CFG with ≦ 10 rules for this language.
Problem 3 (15 pts)
Consider the following CFG,
S → S1│S2
S1 → 0 S1 1│ε
S2 → 1 S2 0│ε
Convert the CFG to CNF by following the procedure in the textbook. Your number
of rules should be ≦ 13 .
( Hint : you can remove redundant rules after the procudure. )
Problem 4 (20 pts)
Consider the following state diagram of a PDA.
╔═╗─┐ 0,ε → 0
start ─→║q1║←┘
╚═╝
│
│1,0 → ε
│
↓
╔═╗─┐ 1,0 → ε
║q2║←┘
╚═╝
AssumeΣ = {0, 1}
(a) What is the corresponding language ? Give the formal definition of this PDA
including a table for the δ function.
(b) Give a CFG with ≦ 3 rules for this language.
(c) We would like to have a DPDA for the same language. Give the formal
definition including a table for the δ function.
Problem 5 (30 pts)
Use the language and diagram in Problem 4.
(a) Modify the DFA to satisfy:
1. Each link is either push or pop;
2. Single accept state;
3. Stack is empty before accepting a string.
Your diagram should have ≦ 4 states.
( Hint : you may introduce extra symbols in the stack. )
(b) Use (a) and the procedure in Lemma 2.27 to generate a CFG for the language.
(c) Is it possible to simplify results in (b) to those in Problem 4 (b) ?
(d) Give two strings s1 and s2 with │s1│=│s2│= 3, s1, s2 ∈ {0,1}*, and s1
is accepted while s2 is rejected. Use the PDA obtained in (a) to simulate
the two strings. Note that you must draw trees like what we did in the
lecture (it is similar to how we simulate NFA).
Problem 6 (20 pts)
Consider the language
2^n
{0 │ n ≧ 0}
We would like to a 2-tape TM to recognize the language by following procedure:
Repeat
1. Copy half of tape 1 to tape 2 and make tape 1 empty;
2. Copy tape 2 back to tape 1;
until tape 1 is empty.
(a) Please give a state diagram for this TM. The number of states should be ≦6
(including q_a and q_r).
(b) Simulate the strings "ε" (i.e., empty string), "0000", and "000000"
Please note that the movement of the head can be L, R, and S.