※ [本文轉錄自 NTU-Exam 看板 #1MCXKIF5 ]
作者: eddy1021 (eddy) 看板: NTU-Exam
標題: [試題] 104上 林智仁 自動機與形式語言 期中考1
時間: Thu Oct 29 20:46:07 2015
課程名稱︰ 自動機與形式語言
課程性質︰ 資工系大三必修
課程教師︰ 林智仁
開課學院： 電機資訊學院
開課系所︰ 資訊工程學系
考試日期（年月日）︰ 2015/10/27
考試時限（分鐘）： 135分鐘
試題 :
● Please give details of your answer. A direct answer without explanation is
not counted.
● Your answer 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(35 pts)
1.(5 pts)Consider the following language of having only one string:
A = {a}.
Assume Σ= {a}. What is the NFA diagram with the smallest number of states
for this language? Give the formal definition. You need to prove yours has
the smallest number of states.
2.(5 pts)If Σis changed to
Σ= {a,b},
what are the new diagram and the new formal definition?
3.(5 pts)Now consider the language
A = {a,b}.
Assume Σ= {a,b}. What is the NFA with smallest number of states for this
language? No need to give the formal definition. You need to argue yours
has the smallest number of states.
4.(10 pts) Use the procedure in the textbook to convert the NFA in 1.3 to
DFA. Reduce it to have the smallest number of states. No need to give the
formal definition. You need to explain yours has the smallest number of
states.
5.(5 pts) For the same language, we consider
{a,b} = {a} U {b}.
For {a} and {b}, we can have two NFA diagrams for them from 1.1. Consider
the way in Theorem 1.45 of textbook to do union of two NFA. What are the
resulting diagram and the formal definition?
6.(5 pts) Convert the above NFA diagram to DFA. If the number of states is
too many, you need to explain why some are not necessary so you don't draw
them. Reduce the DFA to the smallest number of states. Is the resulting
DFA the same as that of 1.4?
Problem 2(35 pts)
Consider the following two language. Let Σ= {0,1}.
W0 = { w | w ends with 0 } (e.g., 000, 100, 11010)
W1 = { w | w ends with 1 } (e.g., 111, 001, 01101)
1.(5 pts) Give a DFA of two states for each of the above languages. Then,
use the technique described in textbook chapter 1.3 to generate an NFA for
W0 o W1.
2.(5 pts) Use the procedure in textbook chapter 1.2 to convert 2.1 to a DFA.
3.(5 pts) Give the regular expression for W0 o W1. The number of the
characters(including \intersection,\union,(,),* but not o,{,} ) should be
≦15.
4.(10 pts) Consider the DFA in 2.2. Use the procedure in textbook chapter
1.3 to get a GNFA and obtain a regular expression. Can you explain that it
is equivalent to that of 2.3?
5.(10 pts) If we consider the NFA in 2.1 and apply the same procedure in
2.4, what is the resulting regular expression? Is the result equivalent to
that of 2.4? Assume your NFA in 2.1 has 4 states q1,...,q4 from left to
right. Use the order of q4, q3, q2, q1 to remove states.
Problem 3(30 pts)
1.(15 pts) Let Σ= {a,b,c}
D = { w | w contains the same number of substrings ab, bc, ca,
but does not contain substring like ac, cb, ba }
Is D a regular language? Prove or disprove it.
2.(15 pts) Let Σ= {a,b,c}
D = { w | w contains the same number of substrings ab, bc, ca, ac, cb, ba }
Is D a regular language? Prove or disprove it.
================================== 試題完 ===================================