課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰林智仁
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2011.12.13
考試時限（分鐘）：
試題 :
˙ 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 (15 pts)
Convert the following CFG into CNF with Σ = {a, b}.
S → bS│E│ε
E → aEb│a
And please follow the formal procedure, i.e. Theorem 2.9 of the textbook.
Problem 2 (20 pts)
Consider the following language
{w│2n1(w) ≦ n0(w) ≦ 3n1(w)}
where Σ = {0, 1} and n0(w) (or n1(w)) means the number of 0's (or 1's) in w.
Construct a PDA with ≦ 5 states to recognize this language. Give the formal
definition of your PDF.
Problem 3 (20 pts)
Consider the following PDA with Σ = {0, 1}
┌─┐ε, ε→ $ ┌─┐─╮ 0, ε→ 0
start ─→│q1│─────→│q2│←╯ 1, ε→ 1
└─┘ └─┘
│
│ 1, ε→ε
↓
╔═╗ ┌─┐ 0, 0 →ε
║q4║←─────│q3│←╮ 1, 0 →ε
╚═╝ ε, $ →ε └─┘─╯ 0, 1 →ε
1, 1 →ε
(a) What is the language?
(b) Draw the tree to process the string 011. Your tree must be complete. Note
that we mean a tree to process an input string. We do not mean a parse
tree of CFG.
(c) Find CFG of this PDA's language. You are required to follow the same
procedure in lemma 2.27 to generate rules. You should not remove any
redundant rules generated by the lemma.
Problem 4 (15 pts)
(a) Construct a Turing machine (i.e., showing the state diagram) for the
language
n n
{ 0 1 │ n ≧ 0 }.
Note that we use the standard Turing machine rather than extensions such
as nondeterministic Turing machine. The number of states is ≦ 6,
including q_a and q_r. You can assume Σ = {0, 1}.
(b) Give the formal definition.
Problem 5 (15 pts)
Consider the language
{w#w│w ∈ {0, 1}*},
where Σ = {0, 1}.
(a) Construct a 2-tape Turing machine to recognize this language. We assume
that
1. in the beginning, 凵(input) in the 1st tape.
2. we copy the second part to the 2nd tape and then compare strings in
both tapes.
3. the number of states (including q_a and q_r) should be no more than 8.
No need to give the formal de nition.
(b) Simulate two strings 01#01.
Problem 6 (15 pts)
Construct a nondeterministic Turing Machine with no more than 7 states
(including q_a and q_r) to recognize the following language:
R
{ww │w ∈ {0, 1}*},
where w^R is the reverse of a string. No need to give the formal definition.