We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

www.vustudents.ning.com

Looking For Something at vustudents.ning.com? Click Here to Search

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

How to Add New Discussion in Study Group ? Step By Step Guide Click Here.

# CS402 Theory of Automata Assignmnet#05 Solution & Discussion

pleas upload it porperly...............

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?

See Your Saved Posts Timeline

Views: 172

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

+ Click Here to Search (Looking For something at vustudents.ning.com?)

### Replies to This Discussion

keya yeh jawab saheeh hay .
Q={ ababa , aabbbbbbb,baabba , babbaaaaaa }
R={ aababa , bbaabba , bbaababa, aaaabbbbbbb, abbabbaaaaaa}
The prefix ababa is in the string bbaababa, aababa
The prefix aabbbbbbb is in the string aaaabbbbbbb
The prefix baabba is in the string bbaabba
The prefix babbaaaaaa is in the string abbabbaaaaaa
i think man ya is tara ho ga.
{a,b,aa,ab,bba} mean Q in R
Friends here is idea solution of cs402 theort of automata.
Question No 1: Marks: 5

Find the prefixes of Q in R where Q and R are languages given below:

Q={ ababa , aabbbbbbb,baabba , babbaaaaaa }

R={ aababa , bbaabba,bbaababa, aaaabbbbbbb, abbabbaaaaaa}
observe ababa,aabbbbbbb,baabba,babbaaaaaa r at the ending part of R
so
Prefix(Q in R)= {a,b,bba,aa,ab}
Question No. 2

By marking the states, decide whether the following FA accepts any word or not? Marks: 5

Note: Show all steps

step1:
marke q0
step2: eliminate q0 and mark q3
step3:eliminate q3 and loop
step4:mark q2
step:eliminatin transitin q2 to q3 se that only 2 transition r left.q4 to q3 and q4 to q2.
in this all process no final stat is marked
Hence our FA accept no words.
Question No. 3 Marks: 5

Describe the language (in English) generated by the following CFG:

S  XY
X  aX | bX | ^
Y  baa | bab | bba | bbb
we see X generates ^,a,b while Y generates baa,bab,bba,bbb
Thus X generates the strings generated by (a+b)* and Y generated baa,bab,bba,bbb
hence we conclude that our cfg generates the string having at least 3 letters starting from b.
Question No. 4 Marks: 5

Construct the CFG that generates the language L = {w  {a, b}*: length(w)  2 and w begins with b and ends in aa or bb}.

Solution:
SXAY | bb
Xb
Y aa | bb
A aY| bY| ^
It is just an IDEA Solution

Q. No.1

Q={ ababa , aabbbbbbb,baabba , babbaaaaaa }

R={ aababa , bbaabba,bbaababa, aaaabbbbbbb, abbabbaaaaaa}

observe {ababa,aabbbbbbb,baabba,babbaaaaaa} at the ending part of R

so the

Prefix
(Q in R)= {a,b,bba,aa,ab}

Q. No. 2

step1:

Marke q0
step2:

Eliminate q0 and mark q3
step3:

Eliminate q3 and loop
step4:

mark q2
step:

Eliminatin transitin q2 to q3 se that only 2 transition r left.q4 to q3 and q4 to q2.

In above all process no final state is clear

Hence, our FA accepts no words.

Q. No. 3

We see

X generates ^,{a, b}

While Y generated {baa,bab,bba,bbb}

Thus,

X generated the strings generated by (a+b)* and Y generated {baa,bab,bba,bbb}

hence,

We find that our CFG generates string having at least 3 letters starting from b.

Q. No. 4

Solution:

X A Y | bb  S

b  X

aa | bb  Y

aY| bY|  A ^

See the attached file pls
Attachments:
keya sub ko neeend aachukey hay . jagoo jagoo subha hoo chukey hay .
keya koi jawab danay wala nahein ?
nai
vu k sary log bht selfesh hai
sub nai....... kuch kuch
excuse me
un kuch kuch mai apka name 1st hai
apko itna kuch ata hai kisi k tory se b help nai kar sakty hai?
kr sakta hoomm ham kuch log annual k liay combine study kr rahe hain .... on mobile conference ....you can join ..... aur sunain....... ?
keya koi hamarey bat soonnay wala hay ?
Allah sub ki sunta hay....... ap Allah se help ki request kue nai krte .....

## Latest Activity

2 minutes ago
zoobi noor liked Zainab Mughal's blog post LAMBA DHAGA AUR LMBI ZUBAN
2 minutes ago
3 minutes ago
zoobi noor liked +¢αяєℓєѕѕ gιяℓ's discussion ٹی وی پر ڈرامہ چل رہا تھا
5 minutes ago
5 minutes ago
Imran bs(i.t) updated their profile
9 minutes ago
Desert11 Hakru joined + M.Tariq Malik's group

### MGMT615 Transportation & Logistics Management

13 minutes ago
15 minutes ago
16 minutes ago
16 minutes ago
16 minutes ago
Desert11 Hakru posted a status
"Pakistan's nuclear sites are less confidential than the past papers of Mgmt615 & 617. So forget abput finding the latter."
16 minutes ago

1

2

3