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 as as bs}. [3 marks]

Q2 Define the langauge L = {a^mbⁿ : 0£m<n} with a context-free grammar. [2 marks]

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 as as bs} 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]