課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰項潔
開課系所︰資訊系
考試時間︰11.23
試題 :
1.Show that (11)^(n+2) + (12)^(2n+1) is divisible by 133 for n = 1,2,...
2.For any string w = w1w2w3...wn,the reverse of w ,written wR,is the string
w in reverse order , wn...w2w1.For any language A,
let AR = { wR | w is belong to A}.Show that if A is regular,so is AR.
3.Prove of disprove the following for regular expression r and s.
A.(rsUr)*r = r(srUr)*
B.s(rsUs)*r = rr*s(rr*s)*
C.(rUs)* = r*Us*
4.Give a PDA recognize the following language L:
L = {w#x | wR is a substring of x , for w ,x are belong to {0,1}*}
5.Prove that the following language L is not a context-free language:
L={(a^i)(b^j)(c^k)| j = max {i,k}}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.229.23.52