课程名称︰自动机与形式语言
课程性质︰必修
课程教师︰林智仁
开课学院：电机资讯学院
开课系所︰资讯工程学系
考试日期（年月日）︰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$