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

 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

# CS402 Theory of Automata Assignmnet#05 Solution & Discussion

+ 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?

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)

### 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

Amen Ch replied to ♦_"Tooba"_♦'s discussion Quize NO#1 in the group CS201 Introduction to Programming
9 minutes ago
Amen Ch joined + M.Tariq Malik's group

### CS201 Introduction to Programming

9 minutes ago
10 minutes ago
11 minutes ago
zohaib iftikhar posted discussions
11 minutes ago
+ ! ! ! ! ! ! 11 updated their profile
12 minutes ago
12 minutes ago
35 minutes ago
51 minutes ago
58 minutes ago
58 minutes ago

1

2

3