课程名称︰自动机与形式语言
课程性质︰必修
课程教师︰林智仁
开课学院：电机资讯学院
开课系所︰资讯工程学系
考试日期（年月日）︰108.1.7
考试时限（分钟）：160
试题 :
Introduction to the Theory of Computation
Final Exam
January 7, 2019 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 (20 pts). Consider f(n) = e^(-n), g(n) = sin n + 2.
(a) (10 pts) Use the definition of Small-O check whether f(n) = o(g(n)) or not.
Do NOT directly calculate the kimit. That is, you need to consider/apply the
definition of limit.
(b) (10 pts) Use the definition of Big-O to check whether f(n) = O(g(n)) or
not.
Problem 2 (10 pts). Suppose f(n) = 2^O(n^3). Is f(n)^3 = 2^O(n^3)? Please
provide detailed explanation.
Problem 3 (20 pts). Consider the language {w#w | w∈{0,1}* }.
(a) (15 pts) Design a 2-tape TM with no more than 6 states (including q_reject)
to recognize the language. Note to simplify the figure, you don't need to
draw q_reject and the transitions going to it. The strategy should be to
● copy first w to the second tape
● move head of the second the to the begining
● compare contents in the two tapes
We require thae Γ = {0, 1, #, ∪}. Note that
● For the two-tape TM, we have
δ: Q×Γ^2 → Q×Γ^2×{L,R,S}^2
● There is no ∪ before the input
(b) (5 pts) Simulate
01#01
by using machine obtained in (a) and the standard TM in Example 3.9 of
textbook. Compare the number of stepd needed by the two machines. You need
to show every step of the simulation.
Problem 4 (20 pts). Consider the language {ww^R | w∈{0,1}*}, where w^R is the
reverse of w.
(a) (15 pts) Give a two-tape non-deterministic TM with no more than 5 states
(including q_reject) to recognize this language. Note that here we allow S
(stay moves) to make the problem easier.
(b) (5 pts) Simulate the path (not the entire tree) that leads to the
acceptance of 0110.
Problem 5 (30 pts). A CNF <V,Σ,R,S> satisfies that R contains only the
following types of rules.
Type-V: A→BC
Type-T: A→a
Type-E: S→ε
when a a∈Σ, A,B,C∈V, and B,C ≠ S. Let
I_CNF = {<G> | G is a CNF and |L(G)| = ∞}
be the set of CNFs that generates an infinite number of strings, where |L(G)|
is the number of strings in the language L(G) of G. Various ways may be
possible to prove that I_CNF is decidable, but wr would like you to answer
the following sub-problems for a step-by-step proof.
(a) (5 pts) Consider a CNF G = <V,Σ,R,S>, If now we consider only type-V
rules, then the partial parse trees(not involving type-T and type-E rules)
are binary trees where every node is a variable. For example, let
G_a = <{S,A,B},{a},R,S>.
where R contains the following rules.
S→AB|ε
A→BB|a
B→AA
An example of partial parse tree is shown below.
S─B─A
│ └A
└A─B
└B─A
└A
We say a partial pare tree generates a string w if it can be extended (with
all rules in R) to a parse tree for w. For instance, the above partial tree
can be extanded to the following parse tree generating aaaaaa. (Note that we
say "if it can be." That is, a partial parse tree may not be able to generate
any string; see sub-problem (b).)
S─B─A ───a
│ └A ───a
└A─B ───a
└B─A──a
└A──a
We define the height of a partial parse tree to be the maximum number of edges
in paths starting from the root. Note that the height of the example in Figure
2 is 3.
By the similar reasoning of pumping lemma, if some non-S variable appears at
least twice in a path from root, then the looping part between the two
occurrences can be repeated as many times as we want and therefore the partial
parse tree can be extended to as large height as we want, and vice versa. For
example, the partial parse tree shown above contains paths S-A-B-A where A
appears twice, and indeed <G_a>∈I_CNF.
● Show that any partial parse tree contains an odd number of nodes.
● For any given CNF <V,Σ,R,S>, find an odd value z so that for any of its
partial parse tree, if
#nodes >= z,
then some non-S variable must appear at least twice in a path from the
root of the partial parse tree.
Hint: You may directly use the fact that if the height of a bonary tree
is no more than h, then
#nodes <= 2^(h+1) - 1.
(b) (5 pts) We are about to argue that partial parse trees generate long
strings if the height is large, but there is one subtle issue that needs
considerayion. Consider
G_b = <{S,A,B},{b},R,S>.
where R contains the following rules.
S→AB|b
A→AA
B→b
G_b can have a partial parse tree of height as large as we want (by
repeatedly applying the rule A→AA), but L(G_b) = {b}! This is because A is
non-deriving. i.e. A cannot derive any string of literals. For example, the
following partial parse tree cannot generate any string.
S─B
└A─A
└A
Therefore we would like to remove all the non-deriving variables before our
argument. Assume we already have a decider D for E_CNF = {<G>|G is a CNF and
L(G)=Ø}. Use D to design an algorithm that finds out all non-deriving
variabls of a given CNF.
(c) (5 pts) Given a CNF G, we can apply the algorithm in (b) to find out all
the non-deriving variables, remove them fome V, and remove all the rules
involving any of them, getting a new CNF G'. It's clear that L(G) = L(G').
Because obtaining G' from G is a decidable procedure, we can now assume that
the CNF G considered has no non-deriving variable.
Show that for a CNF without non-deriving variables, any partial parse tree of
height h > 0 cna generate at least one string, and that the strings w it
generates satisfy |w| >= h+1.
(d) (10 pts) Wrapping up our previous results, given a CNF G without
non-deriving variable (by (b)), if there are enough nodes in any partial
parse tree of G, by (a) the partial parse tree can be extended to as large
height as we want, and therefore by (c) it can generate strings as long as
we want.
Use the above properties to derive an algorithm that decudes I_CNF.
(e) (5 pts) Run your algorithm in (d) on <G_a> in (a) and <G_b> in (b). You
don't need to provide details of running the algorithm in (b).