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: