Theory of Automata BSCS 5 Semester/Term UOS — University of Sargodha 2016

University of Sargodha(Mid Term Examination 2016)

Subject: TOA Total Marks: 30 BSCS 5th (Reg+SS1) Time Allowed: 90 minutes

Q:1 Design finite automata and write regular expression for the following languages over the set

of alphabets {0, 1}. [9+9]

a) {w/w is the binary representation of a number that is divisible by three}.

b) {w/w has length at least 3 and third symbol is a 0}

c) Set of all strings in which the difference of number of 0's and number of 1's is odd.

Q:2 Design FA and convert that FA into regular expression. {a,b} [6]

A language that contain all the words having 2nd last character 'a'.

Q:3 Let's define a new operation, symmetric difference over languages. The symmetric

difference of two languages L and M is the set of strings that are in exactly one of L and M. Prove

that if L and M are regular, so is the symmetric difference of L and M. [6] Note: Take any two

languages and apply the constructive algorithm that proves the above statement.