※ [本文转录自 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.