Theory of Automata BSCS 5th Term Past Paper UOS

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.