課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰林智仁
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰107.12.3
考試時限（分鐘）：160
試題 :
Introduction to the Theory of Computation
Midterm 2
December 3, 2018 10:20-13:00
● Please write your answers in English.
● Please give details of your answers. A direct answer without explanation
is not ciunted.
● Read the problem statements carefully.
● During the exam, you are not allowed to borrow others' notes.
● The problems may not be ordered according to difficulty. Try to work on
easier problems first.
Problem 1 (10 pts). Transform the following CFG to Chomsky Normal Form(CNF).
S→00S|0A|1A
A→11A|ε
Problem 2 (35 pts). Consider the language
L = {ww^R|w∈{0, 1}*},
where w^R denotes the reverse of w.
(a) (5 pts) In th lecture/textbook we showed a 4-state PDA for L as follows.
ε, ε→$ ─┐ 0, ε→0
→q1─────→q2←┘ 1, ε→0
│
│ε, ε→$
│
↓
(q4)←─────q3─┐ 0, 0→ε
ε,$ → ε ←┘ 1, 1→ε
Draw the trees of running
● 0110
● 1010
You need to show all nodes that can be reached by ε links.
(b) (10 pts) For the language L, give a CFG with one variable and 3 rules.
Explain in detail why it has the smallest number of rules.
(c) (10 pts) For the CFG obtained in (b), generate a corresponding PDA with
the procedure in Lemma 2.21 of the textbook.
Draw the tree of running 0110. You need to show all nodes that can be reached
by ε links. Hint: There must be at least 25 nodes; otherwise it is wrong.
(d) (10 pts) Now we would like to generate a corresponding CFG with the
procedure in Lemma 2.27 of the textbook. There are three required feature for
the PDA:
(i) It has a single accept state.
(ii) It empties its stack before accepting.
(iii) Each transition either pushes one symbol onto the stack or pops one off
the stack, but not both at the same time.
Dose the PDA in (a) satisfy all of them? If so, briefly show why each
requirement is satisfied. If not, give a PDA with no more than 5 states
satisfying the requirements. You are NOT allowed to change Σ or Γ.
Than generate the corresponding CFG and give its formal definition.
Problem 3 (30 pts). Consider the following NFA for the language M described by
the regular expression (01)*
0
─────→
→(q1) q2
←─────
1
(a) (10 pts) Give a CFG with one variable and the smallest number of rules for
M. We further require that the total lengths if the rules is minimized.
Explain why yours satisfies this requirement.
(b) (10 pts) Now we modify the edges of the NFA to make it become the following
PDA.
0, ε→ε
─────→
→(q1) q2
←─────
1, ε→ε
Does the PDA satisfy all the requirements in Lemma 2.27? If not, give a
modified PDA with Γ = {0} to meet the requirements.
Then apply the procedure in Lemma 2.27 to generate a CFG for M. You may use
A_ij to represent A_qi,qj for simplicity.
(c) (10 pts) From the CFG obtained in (b), extract a small subset of no more
than 7 rules, then further simplify these rules to your solution in (a).
Hence this procedure shows that the subset of rules you choose can generate
M.
Hints:
● You may need to apply similar techniques for transforming a CFG to CNF.
● At some point you may need to extract several rules again in order to
generate your solution in (a).
● You may need to use the fact that the sets of rules in (a) and (b) both
generate M.
Problem 4 (25 pts). Consider the language
{w$|w∈{0, 1}*, #0(w) = #1(w)},
where #i(w) is the number of occurences of i in w.
(a) (10 pts) Design a PDA with no more than 3 states for this language. We
further require that Γ={0, 1, $}. Explain why it is not a deterministic PDA
(DPDA).
(b) (15 pts) Design a DPDA with at most 8 states for this language. We still
require that Γ = {0, 1, $}. Hint: To avoid non-determinism, you may
transform a transition ε to two.
Simulate and draw the trees of running
● 0011$
● 1$