CS402 Assign 2 Solution Fall 2018

**Don’t relay on my solution. Make changes before upload. I will not be responsible for your marks.**

““““““““““““““““““““““““““““““““““““““““`

Objectives:

Objective of this assignment is to assess
the understanding of students about

the concept of Regular languages, Complement
of a language, Myhill Nerode theorem, Quotient of a language, Prefixes of a
language.

Instructions:

Please read the following instructions
carefully before submitting assignment:

You should consult the
recommended books, PowerPoint slides and audio lectures to clarify your
concepts.
You are supposed to submit
your assignment in .doc format.
Any other formats like scan images, PDF, zip, rar and bmp etc will not be
accepted.
It should be clear that your assignment will not get any
credit if:

·
The assignment is submitted after
due date.

·
The assignment is copied from
Internet or from any other student.

·
The submitted assignment does not
open or file is corrupt.

Note: No assignment will be accepted
after the due date through email in any case (load shedding, server down, internet
malfunctioning etc.).

It is recommended to upload
solution file at least two days before its closing date.

For any query about
the assignment, contact at cs402@vu.edu.pk

Question No 1: Marks=5

Using Myhill Nerode theorem, prove that
the language L defined over Σ={a,b}
containing at least one ‘a’ is regular.

Hint: Define classes and build an FA

Question No 2:
Marks=5

Find the complement of the given
FA.

Question No 3:
Marks=5

Let Q={a,bb,aaab} and R={aba,
aab, bab, baaab, bbbabab, babab, abbbb, bbbb, abbabb, abbbababab}

Find Pref (Q in R).

= ab , abb, bb, abba, b

DOWNLOAD SOLUTION

VU Vicky