SE307 - Computation and Complexity Theory

Test 3

Thursday 12 December 2002, 13:00, Lab 4

T Naughton, CS NUIM,
Back to SE307 home

Remove everything from your desk except pens/pencils. Paper will be provided. Turn off all computer monitors. Answer all questions. Remember to be mathematically precise in all of your answers. You have until 14:50. You can leave whenever you are finished.

Name......................................... Student number.........................

Q1 Construct the state diagram for a pushdown automaton that accepts the language *L* defined as *L* = {*w* : *w*Î{*a*,*b*}*, *w* contains a different number of *a*s as *b*s}. **[3 marks]**

Q2 Define the langauge *L* = {*a ^{m}b^{n}* : 0£

Q3 Give an example of (i) a context-free language that can be accepted by a deterministic pushdown automaton, and (ii) an example of a context-free language that cannot be accepted by a deterministic pushdown automaton. **[2 mark]**

Q4 Three distinct proofs are required to prove that the set of regular languages is a proper subset of the set of context-free languages. For each of these three proofs, state what the proof is, and outline with one sentence how you might prove it. **[3 marks]**

Q5 Describe using one short sentence, what is required to prove that an *n*-stack pushdown automaton (*n*>2) is no more powerful than a 2-stack pushdown automaton. **[1 mark]**

Q6 Prove that the language of finite-length decimal numbers between 0 and 1 (inclusive) is countable. [For example, 0.1 and 0.54321 are finite-length decimal numbers, but the decimal expansion of one third (0.3333333...) is not because its decimal expansion is not finite in length.] Your proof must take the form of either (i) an infinite-loop computer program to print out a lexicographical ordering of *L*, (ii) a mathematical description of a bijection between *L* and the natural numbers, or (iii) a list of the first 25 or so mappings such that it is obvious that such a mapping exists. **[2 marks]**

Q7 Find two words in the language *L*={*w* : *w*Î{*a*,*b*}*, *w* contains twice as many *a*s as *b*s} that cannot be pumped according to the rules of the pumping lemma for regular languages. (Just state the words, you don't have to prove anything.) **[2 marks]**