www.vustudents.ning.com

We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.

# CS402 Assignment#01 Solution & Discussion Due Date:08-11-2010

Objectives
Objective of this assignment is to make students able to understand the following concepts,
Recursive Definition of a language
Regular Expression
Finite Automata

Recursive Definition:
Question No.1
a. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings starting with a or
b
a. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings ending with aa.
b. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings NOT ending
with a.
c. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings NOT ending
with bb.
d. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings having aa at any
place.
e. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings NOT having aa
at any place.
_______________________________

Regular Expressions:
Question No.2

Give Regular Expression for each of the following language defined over alphabet Σ = {a, b}
b. Language having all strings STARTING with a or b
c. Language having all strings NOT having ab
d. Language having all strings NOT having bb
e. Language having all strings HAVING aa
f. Language having all strings HAVING bba
g. Language having all strings NOT having two consecutive a’s
h. Language having all strings NOT having even no of a’s and b’s
________________________________________

Finite Automaton:
Question No.3
Give Finite Automata for each of the following language defined over alphabet Σ = {a, b}
a. Language having all strings STARTING with a or b
b. Language having all strings NOT having ab
c. Language having all strings NOT having bb
d. Language having all strings HAVING aa
e. Language having all strings HAVING bba
f. Language having all strings NOT having two consecutive a’s
g. Language having all strings NOT having even no of a’s and b’s

_____________________________________

RE to FA and FA to RE conversion:
Question No.4

Convert FA’s of the following two languages you have already made in Question No.3 to RE’s using procedure
given in Kleene’s theorem and verify RE with your given RE in question 2.
a. Language having all strings HAVING aa
b. Language having all strings NOT having two consecutive a’s
___________________________

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

Upload single doc file having solution of all these questions.
________________
For complete assignment,see the attached file pls

Views: 1020

Attachments:

### Replies to This Discussion

Q 2 (b) a(a+b)*+b(a+b)*
(c) (a+b)*(ba+bb+aa)
(d) (a+b)*(ab+ba+aa)
(e) (a+b)*aa(a+b)*
(f) (a+b)*bba(a+b)*
(g) ------
(h) ((a+b)(a+b)*(a+b)

Please suggest modification if not correct.
AOA
kya ap ne different strings ko in RE k thru check kiya hai....?

jese (c) k answer m ban'ne wali string main ab ni aana chahiye tau kya (a+b)*.... ab ki string generate ni karti........karti hai...
check it again.plz
muje khud b kafiii prob ho rahi hai
thanx. i am working on it.
janleva007@yahoo.com
janleva009@gmail.com
g= ab*a or (a+b)*(ba+bb)
yar kashif
(a+b)* (ba+bb)
if we suppose (a+b)* ,,,,,,,, (*) is 2 here then
strings will be as such
{aaba, aabb, bbba, abba, babb}
if your RE is correct consecutive a`s are generated please, may be i am wrong clear this point to me please thanks for your time
use this one ab*a
3. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings NOT ending with a.
Step 1: a and b are in Language L
Step 2: (s)b is also in language L, Where s belongs to .......Segma star
Step 3: No strings except those constructed in above, are allowed to be in L
is recursive def k step 1 main sirf b hona chahiye..a ni
STEP 1: b in in the Language L
a bhi language ka part ho sakta hay....... like as {aab, ab, abab}
hm hmesha step 1 words btate hain jo k lang m hon ...means ek poori string... ksi string ki substring ni.....have u got my point

1

2

3

4

5

## VIP Member Badge & Others

------------------------------------

## Latest Activity

30 seconds ago
Laila kabeer posted discussions
1 minute ago
4 minutes ago
12 minutes ago
1 hour ago
+ ! ! !★ "Areena"★✓ and Anu Shay are now friends
1 hour ago
ልጠክል ጌዘልፕፕጎ liked + ♥ Haniya khan's discussion (Bal-e-Jibril)
1 hour ago
Z@¥¥@N R@JPuT posted a discussion

1 hour ago