※ [本文转录自 NTU-Exam 看板 #1IYlb7Nb ]
作者: ibetrayall () 看板: NTU-Exam
标题: [试题] 102上 林智仁 自动机与形式语言 期中考2
时间: Tue Nov 19 13:38:12 2013
课程名称︰自动机与形式语言
课程性质︰
课程教师︰林智仁
开课学院：电资学院
开课系所︰资讯工程系
考试日期（年月日）︰102/11/19
考试时限（分钟）：10:25 ~ 13:25
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
‧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 athers' class notes.
‧Try to work on easier questions first.
Problem 1 (10 pts)
Consider the following PDA.
ε,ε → $
─┐ 0,ε → 0
start →《q1》─────→ q2 │
←┘ 1,ε → 0
│
│ ε,ε → $
│
↓
─┐ 0, 0 → ε
《q4》←───── q3 │
←┘ 1, 1 → ε
ε,$ → ε
Problem 2 (10 pts)
Consider the following grammar with Σ = {a,b}.
S → ASB
A → SA | AB | a | ε
B → SBS | A | bb | ε
Find the Chomsky normal form. You must show details of the procedure and
follow the order of steps below.
‧add S_0 → S
‧remove V → ε
‧remove V_1 → V_2
Problem 3 (80 pts)
Consider Σ = {0,1} and A = { w | w ∈ Σ* and has an even number os 0s}.
Please answer the following questions.
(a) (5 pts)
Draw a 2-state DFA diagram for this language.
(b) (5 pts)
Follow the way described in our lecture to have a 5-rule CFG for this
language. The main idea is that if DFA has
δ(p,a) = q,
then we add a rule
S_p → aS_q.
(c) (15 pts)
Does this CFG has the smallest number of rules? If yes, explain why.
If not, give a CFG with the smallest number of rules.
Please prove that the CFG you gave has the smallest number of rules.
Note: the proof may be a little bit difficult. You may work on
subsequent sub-problems first.
(d) (10 pts)
For CFG obtained in (b), obtain a PDA using the procedure in our proof
of the equivalence between PDA and CFG. (Lemma 2.21)
(e) (10 pts)
The PDA obtained in (d) apparently does not have the smallest number
of states . Give a PDA with only two states for this language. You don't
need to give the formal definition. A state diagram is enough.
(f) (10 pts)
Modify the PDA obtained in (e) to satisfy the following conditions needed
in Lemma 2.27:
- It has a single accept state, q_accept.
- It empties its stack before accepting.
- Each transition either pushes a symbol onto the stack (a push move)
or pops one off the stack (a pop move), but it does not do both at
the same time.
We require you to use three states and no more than six edges in your
answer. The one pointing to the start state is not counted as an edge.
You must explain why for your answers these conditions are satisfied.
Hint: you may need to adjust your answer for (e).
(g) (10 pts)
Use the PDA obtained in (f) to generate the corresponding CFG by method
in Lemma 2.27.
(h) (5 pts)
Check if you can use the CFG obtained in (g) to generate the following
strings:
- 0011
- 01000
(i) (10 pts)
Design a DPDA for this language with the smallest number of states. You
are required to give its formal definition.
Note that in drawing PDAs, you CANNOT use the shorhand like
q0
│
│ a, s → xyz
↓
q1
注：被《》括住的代表 accept state 。