[試題] 98上 自動機與形式語言 第一次期中考
課程名稱︰自動機與形式語言
課程性質︰資訊系大三必修
課程教師︰林智仁
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰98/10/13
考試時限（分鐘）：150分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Problem 1 (40 pts)
LetΣ={0}. Consider by this NFA:
(a) What is the languagerecognixed by this NFA, and explain how you get this?
0 0,ε 0
start→q1→→→q2→→→q3→→→q4→
↙ ↖ ↖↓0
←← 0
(b) Show a state diagram of the DFA with the smallest possible number of
states for the same language.
(c) Following the procedure in the textbook to trasform this NFA to DFA (i.e.,
using P(Q) as new states)
(d) Can you reduce the diagram obtained in (c) to the DFA in (b)?
Problem 2 (20 pts)
Consider any finite set Σ. In provin that language described by a regular
expression is regular, we construct NFA for R = a,ε and ψ. Could you
construct DFA instead? For each DFA, use the smallest number of states, give
its formal five-tuple definition and show its state diagram.
Problem 3 (15 pts)
Assume Σ={0, 1}. Construct a state diagram of the DFA with the smallest
number
of states of following language:
0*1Σ*1*0Σ*
In additional to the final state diagram, you also need to explain how this
diagram is generated. You don't need to give the formal definition.
Problem 4 (25 pts)
Given a regular langguege A. Define
++
A ≡ {x1x2...xk︱k≧2,xi屬於A, i = 1,...,k}.
++
1. Is A regular? ++
2. If your answer is yes, give the formal definition of an NFA for A . That
is, if an NFA for A is (Q1, Σ, δ1, q1, F1), how to use it to construct an
++
NFA (Q, Σ, δ, q0, F) to recognize A .
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.131
推
10/13 22:04, , 1F
10/13 22:04, 1F
→
10/13 22:42, , 2F
10/13 22:42, 2F