课程名称︰自动机与形式语言
课程性质︰资工系必修
课程教师︰陈伟松
开课学院：电资
开课系所︰资工
考试日期（年月日）︰2017/11/9
考试时限（分钟）：18:30 - 21:30
试题 :
Instructions
‧This is a closed book exam.
‧Write down your name and student number clearly.
‧Write down your solutions clearly.
‧There are FIVE questions altogether.
‧Discussions/collaborations are NOT allowed.
‧All electronic devices must be switched off during the exam.
‧You don’t need to do the questions in the same order as written here.
‧You can use any result discussed, or stated in the class or in the homework.
‧However, if you use results never stated in the class or in the homework
before, you must supply their complete proofs.
‧You can also freely use pumping lemma (for both regular languages and CFL).
Questions
(1)[2 points] Consider the following automaton A over the alphabetΣ ={a,b}.
a a∩
∩ |↓
|↓ ┌───┐ a ┌──┐
┌─┐ b │┌─┐│──────→│ │
→│q │──→││p ││ │ r │
└─┘ │└─┘│←──────│ │
└───┘ b └──┘
(i) Is A deterministic or non-deterministic ?
(ii) Is aaa accepted by A ?
(iii) Is abababababa accepted by A ?
(vi) Construct a deterministic automaton for A .
(2)[2 points] A string ω∈{0,1}^* represent an integer in a standard way.
For example, the string 000 represents the integer zero, and so do 0 and
000000. The string 00100 and 100 both represent the integer 4 .
Construct a DFA for the following language over the alphabet {0,1}:
L_0 := {ω│ω represents an integer divisible by 3}
Hint: Consider (2i+j) mod 3, for every i∈{0,1,2} and j∈{0,1}.
(3)[2 points] In this question alphabet is Σ={0,1,#}.
For a word ω∈{0,1}^* , we denote by ω^R the string obtained by
reversing ω. For example, if ω is 011, then ω^R is 110. Likewise ,
if ω is 000110, then ω^R is 011000. By default, if ω is empty string ε
,then ω^R is ε.
Construct the CFG for each of the following languages.
‧L_1 := {ω#ω^R# | ω∈{0,1}^* }.
That is, L_1 consists of all the words of the form:
u#v#
where u,v∈{0,1}^* and v = u^R.
‧L_2 := {ω_1#ω_1^R#ω_2#ω_2^R ……#ω_k#ω_k^R#|each ω_i∈{0,1}^*
for some k ≧ 1}.
That is, L_2 consists of all the words of the form:
u_1#v_1#u_2#v_2#‥‥#u_k#v_k#
for some k≧1 and for each 1≦i≦k, u_i,v_i∈{0,1}^* and v_i^R=u_i.
(4)[2 points] Prove or disprove the following.
‧If L is regular and K is CFL, then L∩K is regular.
‧If L is regular and K is CFL, then L∪K is regular.
(5)[2 points]For a language L⊆{a,b}^* , we define half(L) to be the
following language.
half(L) := {x | there is y such that |x|=|y| and xy∈L}.
That is , half(L) consists of the first halves of words in L. Prove that
if L is regular, then half(L) is also regular.
解答:
https://drive.google.com/file/d/11xXuefuc0bO9yc2dY0YlP1N-lSApZ7z4/view?usp=sharing