Automata Assignment Two

COMSATS Institute of Information Technology Lahore

CSC312 – Automata Theory (Sec-ABC) – Assignment 2

Wednesday, Sep. 30, 2015

Name: ___________________              Reg. No. ___________________

Time: 15 minutes                             Max. Marks: 30

Qno.1: Construct The DFA from the Given statements of Language over the alphabet set { a b} . (5X3=15)

1. Build a machine that accepts all the strings that have an even length and also not divisible by 6.
2. Language of all those string which do not end by ba.
3. Language of all those strings that accepts only the words baa,ab and abb.
4. Language of all those strings that contains even number of substring ab.(Optional)
5. Language of all those strings of a’s and b’s such that the next to the last letter is an a.(Optional)

QNo.2: Construct The Regular Expression from the Given statements of Language over the alphabet set { a b} . (5X3=15)

1. Make a regular Expression in which all words do not have substring ab.
2. Make a regular expression in which input has no restriction at start but must not have ending with aa or bb. Other possible combinations with which string may end are ab or ba or single letter a or single letter b.
3. Input has no restriction at start but must not be ending with aa or bb. Other possible combination with which string may end are ab or ba or single letter a or single letter b.
4. Make a Regular Expression that do not contain both substring bba and abb. (Optional)
5. Make a Regular Expression in which any b’s that occur are found in clump of an odd number at a time (Optional)

Deadline 15 October at 1400 Hours

…………………………….Best of Luck…………………………………….