CS402 Assignment No. 1 Announced
Sunday, April 17, 2011 Posted In CS and IT Edit This
Theory of Automata (CS402)
Assignment No.1
Deadline
Your assignment must be uploaded before or on 18th April, 2011
Rules for Marking
It should be clear that your assignment will not get any credit if:
o The assignment is submitted after due date
o The assignment is copied
Objectives
Objective of this assignment is to make students able to understand the following concepts,
o Recursive Definition of a language
o Regular Expression
o Finite Automata
Question No.1
RECURSIVE DEFINITION
a. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings STARTING WITH aa OR ENDING WITH bb
b. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings MULTIPLE OF 2
c. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings NOT ENDING with aa or bb
d. Give recursive definition of language defined over alphabet Σ = {a, b}, NOT HAVING ab at any place.
e. Give recursive definition of ODD PALINDROME (PALINDROME WITH
ODD STRINGS ONLY) defined over alphabet Σ = {a, b}
Question No.2
REGAULAR EXPRESSIONS
Give Regular Expression for each of the following language defined over alphabet Σ = {a, b}
a. Language having all strings STARTING AND ENDING WITH ab
b. Language of strings NOT having bb OR aa at any place
c. Language of all strings NOT HAVING aab in start
d. Language of all strings NOT HAVING aab in end
e. Language of all strings HAVING count of b’s multiple of 2 [No restriction on count of a]
Question No.3
FINITE AUTOMATA
Give Finite Automata for each of the following language defined over alphabet Σ = {a, b}
a. Language having all strings with alternating a’s and b’s , some example strings are ababab… or bababa…
b. Language having all strings NOT containing aa at any place
c. Language of all strings NOT STARTING with bb
d. Language of all strings STARTING WITH bba
e. Language having all strings NOT having even no of a’s and b’s
You can view the video tutorial in file,
http://vulms.vu.edu.pk/Courses/CS402/Downloads/Assignment1.
00.zip to see how to make FA in MS Word.
Important Note:
While attempting any question always remember the following points:
o Where OR is used in the description of a language it means that expressions on both sides of ‘OR’ are parts of the language.
o Where NOT is used in the description of the language it means that language includes all strings except described in the ‘NOT’ condition, for example language NOT starting with a, means all strings not having a in the start (you have to evaluate yourself what kinds of strings are these).
Assignment Uploading Instructions:
o Upload single word file having solutions for all parts as well as chart images.
o You can crop and compress images in the word file by double clicking on an image and selecting compress all images option to decrease file size before uploading it.
Solution:
Click the below link for current solved assignment No. 1 of cs402
VUsolutions Solved Assignments
Solution:
Click the below link for current solved assignment No. 1 of cs402
VUsolutions Solved Assignments
