※ [本文轉錄自 NTU-Exam 看板 #1GXkDmrK ]
作者: rod24574575 (天然呆) 看板: NTU-Exam
標題: [試題] 101上 林智仁 自動機與形式語言 期中考1
時間: Wed Oct 24 02:35:23 2012
課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰林智仁
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2012.10.23
考試時限（分鐘）：150分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題：
˙ 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 others' class notes.
˙ Try to work on easier questions first.
Problem 1 (5 pts)
Give the formal definition of the following NFA.
┌─┐ 1 ┌─┐0,1,ε┌─┐0,1,ε╔═╗
start ─→│q1│──→│q2│──→│q3│──→║q4║
└─┘ └─┘ └─┘ ╚═╝
↑│
└┘0,1
Problem 2 (20 pts)
Use the procedure in section 1.2 of the textbook to convert the NFA in
Problem 1 to DFA. Simplify the obtained DFA to have only 4 states. (You need
to first draw ALL possible states and then eliminate unnecessary states.)
Problem 3 (20 pts)
Is the following language regular?
L = {(a^m)(b^n) | m = kn, where k is positive integer}
Explain your answer clearly.
Problem 4 (20 pts)
Is the following language regular?
L = {(a^m)(b^n) | m + n is prime}
Explain your answer clearly.
Problem 5 (25 pts)
Consider the following language
A = {ε}
where the alphabet Σ = {O}.
1. Give a 1-state NFA to recognize this language (diagram and formal
definition).
2. Give a 2-state NFA to recognize this language (diagram and formal
definition).
3. Convert the 2-state NFA to DFA using the procedure in section 1.2 of
the textbook. (You need to first draw ALL possible states and then
simplify it to a 2-state DFA.)
4. Convert the DFA to GNFA and follow the procedure in section 1.3 of the
textbook to obtain the corresponding regular expression.
5. Consider the DFA of subproblem 3. Is the 2-state DFA unique? Why? If you
use 3 states to recognize the language, is there an unique DFA? Why?
Problem 6 (10 pts)
Give a counterexample to show that the following construction fails to prove
the closure of the class of regular languages under the star operation. Let
N1 = (Q1, Σ, δ1, q1, F1) recognize A1, where Σ = {0, 1}. Construct
N = (Q1, Σ, δ, q1, F) as follows. N is supposed to recognize A1*.
˙ The states of N are the states of N1.
˙ The start states of N is the same as the start state of N1.
˙ F = {q1}∪F1
The accept states F are the old accept states plus its start state.
˙ Define δ so that for any q∈Q and any a∈Σ∪{ε},
δ(q, a) = { δ1(q, a) q/∈F1 or a≠ε
δ1(q, a)∪{q1} q∈F1 and a＝ε
The counterexample must be a NFA diagram with the smallest number of states,
and explain your counterexample clearly.