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