Semester: Fall 2016 | Assignment No. 01 SEMESTER Fall 2016 CS402- Theory of Automata | Total Marks: 20 Due Date: 16 Nov 2016 |
Instructions
Please read the following instructions carefully before solving & submitting assignment:
It should be clear that your assignment will not get any credit if:
o The assignment is submitted after due date.
o The submitted assignment does not open or file corrupt.
o The assignment is full or partially copied from (other student or ditto copy from handouts or internet).
o Student ID is not mentioned in the assignment File or name of file is other than student ID.
o The assignment is not submitted in .doc or .docx format.
Uploading instructions
Your submission must include:
- Assignment should be in .doc or .docx format.
- Save your assignment with your ID (e.g. bx020200786.doc).
Assignment submission through email is NOT acceptable
Objective
The objective of this assignment is
o To give knowledge and understanding of Regular Expression.
o To be able to understand and draw the Finite Automata (FA).
Note:
Your answer must follow the below given specifications.
· Font style: “Times New Roman”
· Font color: “Black”
· Font size: “12”
· Bold for heading only.
· Font in Italic is not allowed at all.
· No formatting or bullets are allowed to use.
· Your answer should be precise and to the point, avoid irrelevant detail.
Lectures Covered: This assignment covers Lecture # 01 - 09
Deadline
Your assignment must be uploaded/submitted at or before 16/11/2016.
Question No: 01 (Marks: 05 + 05)
(a) Write a regular expression for the language over an alphabet Σ = {u, v} in which all strings do not end with uu.
Solution : RE = /\ + u + v + (u+v)* (uv+vu+vv)
(b) Write a regular expression for the language over an alphabet Σ = {m, n} in which all strings have number of m’s divisible by 2.
Solution : RE = n*(mn*mn*)* OR (n + mn*m)* OR (n*mn*m)*n*
Question No. 02 (Marks: 10)
Draw (Build) the FA for the language described in question no. 1 part (a).
0 comments: