T Naughton, CS NUIM, Back to SE120 home

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

Q1 Why are language acceptance (language recognition) problems of interest to computer scientists? [2 marks]

Q2 Define the language acceptance problem that corresponds to the problem of taking a list of integers and returning the list sorted in ascending order. [1 mark]

Q3 Let the set X be defined as X={x | x is a real number and 100x is a natural number}. For example, 5.21 is in X and 0.99 is in X. Prove that X is countable. [5 marks]

Q4 For each of the following sets, state whether the set is finite, countably infinite, or uncountable:

• The set of all real numbers less than 10. [1 mark]
• The set of all finite words over a finite alphabet. [1 mark]