Academic year 2002-2003



SE307 Test 2



Solutions



Q1 You could prove that the regular languages are closed under complement by showing that the complement of any regular language is also regular. This could be achieved with the following giving steps:

1) Given any regular language L, construct a DFA called M that accepts L.

2) Modify M as follows:

  i) Convert all accepting states to nonaccepting states

  ii) Convert all nonaccepting states to accepting states



The resulting DFA accepts the complement of L. If the complement of L can be accepted by a DFA then the complement of L must also be regular. Since this sequence of steps can be applied to any regular language, this proves that the regular languages are closed under complement.



Marking scheme:

Correct sequence of steps: 2 marks

A sequence of steps that is slightly wrong: 1 mark

Giving an example of turning an FA into its complement without giving the sequence of steps: 0.5 marks





Q2 Examples such as:

   aaaaab     x=a   y=aa    z=aab

   ba^{p}bbb   x=baa   y=a^{p-2} z=bbb

   aababbaa   x=aab y=a     z=bbaa



Marking scheme:

One correct example: 1 mark

Three correct examples: 2 marks





Q3 Examples such as:

   a^{p}b^{p/2}

   a^{2p}b^{b}

   a^{4p}b^{2p}



Marking scheme:

One correct example: 1 mark





Q4 This language is regular. A suitable regular expression would have the form: eUaUbU(a(aUb)^{*}a)U(b(aUb)^{*}b). It is easy to see what a corresponding finite automaton might look like.



Marking scheme:

Correct FA or regular expression: 2 marks

Correct except for one mistake: 1 mark