CS 402 Theory of Automata Assignment No 1 Fall 2013 Due Date 27/11/2013

Assignment No. 1
Semester: Fall 2013

CS402 – Theory of Automata

Instructions
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).

Assignment

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}

Deadline:
Your assignment must be uploaded on or before November 27, 2013.