课程名称︰ 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.