NUIMCrest CS403 - Computational Complexity Theory
Test 2
Friday 29 November 2002, 15:00, Lab 2

T Naughton, CS NUIM, Back to CS403 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. Write your name and student number below.

Name......................................
Stream (CS/CSSE/MCompSci).................. Student number..........................

Q1 You have been shown a proof that the union or concatenation of two regular languages is a regular language. You have been shown a proof that the Kleene star of a regular language is a regular language. But what about the complement of a language? The complement of a language is defined as follows. Given a language L over an alphabet {a,b} the complement of L is the set of all words in {a,b}* that are not in L, written more formally as Lc={w : wÎ{a,b}*, wÏL}. Prove that the complement of a regular language is a regular language. [2 marks]

Q2 Language L={w : wÎ{a,b}*, w contains the substring aab and contains no more that three bs in total} is a regular language. The pumping lemma says that every word in L that is greater than the pumping length p, can be written as the concatenation of three strings xyz such that pumping y results in another word in L. There are two restrictions on how the word can be written in xyz format:

  • y has to contain at least one symbol,
  • |xy|<=p.
    Illustrate that you know what the pumping lemma means by picking any three words in L that have length at least p=5, and rewrite them in xyz form such that the y part can be pumped. [2 marks]

    Q3 Prove that the language L={w : wÎ{a,b}*, w contains twice as many as as bs} cannot be pumped, by finding at least one word in L, with length greater than p, that cannot be written in the xyz form. (This proves that L is nonregular.) [1 mark]

    Q4 Prove that the language L={w : wÎ{a,b}*, w contains the same number of occurrences of ab as ba} is regular, by supplying a NFA or FA or regular expression to describe it, or prove that it is nonregular using the pumping lemma. [2 marks]