課程名稱︰ Formal languages and automata theory
課程性質︰ 必修
課程教師︰ 陳偉鬆
開課學院： 電資學院
開課系所︰ 資訊工程系
考試日期（年月日）︰2016/11/08
考試時限（分鐘）：180
是否需發放獎勵金：是
試題 :
Instructions
‧DO NOT TURN THIS SHEET UNTIL YOU ARE TOLD TO DO SO
‧This is a closed book exam.
‧Write down your name and student number clearly.
‧Write down solutions clearly.
‧There are four 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 in the class. However, if you see results
not proved in the class, you must supply their complete proofs.
‧You can also freely use pumping lemma(for both regular languages and CFL).
Questions
In the following all the languages are over the alphabetΣ={a,b}.
(1) Consider the following automation A.
a a
╭╮ ╭╮
│↓ │↓ a
┌─┐ b ╔═╗ ───→┌─┐
start →│q │────→║p ║ │r │
└─┘ ╚═╝ ←───└─┘
b
(i) Is A deterministic or non-deterministic?
(ii) Is aaa accepted by A?
(iii)Is abababababa accepted by A?
(iv) Construct the deterministic automation for A.
(2) Determine which of the following languages are regular. Justify your answer
(i) L1={w|w is of odd length}.
(ii) L2={w|w is of odd length and in the middle of w is a}.
(iii)L3={w|there are at least 3 b's in between every two consecutive a's}.
For example: abbba∈L3, and so is abbbbabbbbba∈L3. However, aa∈/L3,
because there is no b in between the first and second a. Likewise,
abbbaba∈/L3, because in between the second and third a there is only
one b.
(iv) L4={w|w is of even length, but the number of a's in w is odd}
(3) Determine which of the following languages are CFL. Again, you should
justify your answer.
(i) L5={w|w is of even length}
n n m m
(ii) L6={a b a b |n,m≧0}
n m m n
(iii)L7={a b a b |n,m≧0}
n n m
(iv) L8={a b a |n≦m≦2n}
(4) A language L is co-finite, if Σ*-L is finite.
Prove that every co-finite language is regular.
n
(5) Consider the language L=(a |n is a prime number). We have leran that L is
not CFL. However, a good friend of mine Bob claims to have proved that on
the contrary, L is CFL. His proof proceeds as follows.
n
Bob's Proof: First, note that for every integer n≧1, the language Ln={a }
is a CFL generated by the following grammer:
n
S -> a
In particular, Lp is CFL, for every prime number p. Now,
L = ∪ Lp
(p is a prime)
Since CFL languages are closed under union, it follows that L is CFL.
What do you think? Is Bob's proof right or wrong? Is there any
inconsistency in automata theory? Please explain.