※ [本文转录自 NTU-Exam 看板 #1Kkthzyp ]
作者: irritum (働いたら 负け) 看板: NTU-Exam
标题: [试题] 103上 林智仁 自动机与形式语言 第二次期中考
时间: Sun Jan 18 17:20:56 2015
课程名称︰ 自动机与形式语言
课程性质︰ 必修
课程教师︰ 林智仁
开课学院： 电资学院
开课系所︰ 资讯工程
考试日期（年月日）︰ 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.