CS402 Theory of Automata Assignment 1 Solution Fall 2013

Assignment No. 1
Semester: Fall 2013

CS402 – Theory of Automata



Please read the following instructions carefully before submitting assignment:

It should be clear that your assignment will not get any credit if:


  • Assignment is submitted after due date.
  • Submitted assignment does not open or file is corrupt.
  • Assignment is copied (From internet/ to from students).




All Questions carry equal marks.


Question No 01:

Write descriptive definition of Odd – Odd language on Σ = {a, b}


Question No 02:

Tokenize the string on Σ = {a, ba, cb, da, db}. String is as under;

String = {bacbabadadbdbbaaadacbaa}


Question No 03:

a – Is the Σ in question number 2 has invalid characters / alphabets?

b – If yes, then write the alphabets which makes Σ invalid. If answer is No then justify in 2 – 3 lines.


Question No 04:

Write RE for language starting with alphabets ab and ending at c while Σ = {a, b, c}


Question No 05: Write RE for language where ‘a’s and ‘c’s are occurred together. While Σ = {a, b, c}

Assignment Solution:

1 2