We have been working very hard since 2009 to facilitate in your learning Read More. We can't keep up without your support. Donate Now.

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

Looking for Something at Site? Search Below

# CS402 Theory of Automata Assignmnet#05 Solution & Discussion

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

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

Views: 201

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

3 minutes ago
Shanzay liked +!!!StRaNGeR!!! +'s discussion غزل
4 minutes ago
5 minutes ago
5 minutes ago
6 minutes ago
6 minutes ago
6 minutes ago
Shanzay liked Hania Ahmed's discussion FACT!!
7 minutes ago

1

2

3