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

2 minutes ago
Waseem Khan posted a discussion

### E-Music SRS

4 minutes ago
+ M.Tariq Malik's 12 discussions were featured
4 minutes ago
+ M.Tariq Malik added a discussion to the group BIO102 Basic II-Chemistry

### BIO102 Current Mid Term Papers Fall 2019 (14 to 26 December 2019) & All Solved Past Papers, Solved MCQs & Helping Material

5 minutes ago
+ M.Tariq Malik added a discussion to the group BIO101 Basic I-Biology

### BIO101 Current Mid Term Papers Fall 2019 (14 to 26 December 2019) & All Solved Past Papers, Solved MCQs & Helping Material

14 minutes ago
16 minutes ago
"mth404 2nd assignment sol plz????????????/"
21 minutes ago

1

2

3