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 Final Term Exam Questions & Solutions

Any one can please solve these questions for other students who has not attempt their paper yet.

4. convert it in CFG..

b+(a+b)+a*

5. Construct FA from the following CFG

S---->abA

A---->baB

B---->aA|bb

6. Convert following CFG into CNF                        (5 marks)

S----->ABC

A----->C|aA

B----->bB|b

C----->cCd|c

7. Convert following CFG into CNF                   (3 marks)

S----->XY

X----->aX|bX|a

Y----->Xa|Yb|a

8. Show following CFG n regular language.

S--->aS

S--->bS
S--->a

S--->b

9. If S={ab, bb, ac, bc}

T={ab, bb, ac, bc, bbbb}

then show or prove that S*=T*

Views: 1086

### Replies to This Discussion

cute doll  you have attempt these questions. can you post answers

ans Q#8

The regular lang defind over sigma{a,b} wiil b xpressd by reg lang. as under.

(a+b)*

Q#5

FA that accepts the grammar  (Æ denotes ---> symbol)
SÆabA
AÆbaB
BÆaA|bb
The language can be identified by the three words generated as follows
S fi abA
fi abbaB (using AÆbaB)
fi abba bb (using BÆbb)
S fi abA
fi abbaB (using AÆbaB)
fi abbaaA (using BÆ aA)
fi abbaabaB (using AÆ baB)
fi abbaababb (using BÆ bb)
S fi abA
fi abbaB (using AÆbaB)
fi abbaaA (using BÆ aA)
fi abbaabaB (using AÆ baB)
fi abbaabaaA (using BÆ aA)
fi abbaabaabaB (using AÆ baB)
fi abbaabaababb (using BÆ bb)
which shows that corresponding language has RE abba(aba)*bb. Thus the FA accepting the given CFG may be
(can't make..tym shrt:(

Q#5 handouts pg 108

Sẙƹᶁᵰ Bύƙҥᵰŗᶖ•  Q5 main you hv write (Æ denotes ---> symbol)

in dono stmbols mai se koi b use ki ja sakti hay?   (Æ  or  --->)

???

or yeh ""fi"" kya chiz hay?? kya yeh (Φ) phi symbol hay ?

--> handouts mn uz hui hy..bt is site pe is tra show ho ri hy..fi ni hy...i can't c d8..!!

handouts pg#108 full ans hy

check d8 plzz!!

9. If S={ab, bb, ac, bc}
T={ab, bb, ac, bc, bbbb}
then show or prove that S*=T*

if v take * of the word (bb)* then we cud hav bbbb, where * =2

while v already have bbbb in T;

there for T8=S8

(this Q from previous lects. i hvnt read d8 y8...so jst a vague idea ...)

myn ppr to ds sub. iz 2moro.

mine is also 12:30 MOnday. but page 108 pay toh unit production and nonunit production ki examples hain. yeh wali toh nahin hay.

can u please take a screen shot and then paste here or attach that image of page? thanks

Sẙƹᶁᵰ Bύƙҥᵰŗᶖ i think in question 9

1st we expand this like

T={aa,bb,ac,bc,ab,cc,....bbbb,....}

S={aa,bb,ac,bc,bbbb,...}

then we make its regular expression.

T={a,b,c}*

S={a,b,c}*

that is showing both the regular expression are same so we can say.

T*=S*

these are my perceptions what do you say?

1

2

3

4

5

## VIP Member Badge & Others

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

## Latest Activity

Mani Siddiqui posted a status
"کسی کا عہد گذشتہ کسی کا حال تھی وہ ہزار نقص تھے اس میں مگر کمال تھی وہ"
22 minutes ago
naveed asmat mirza joined + M.Tariq Malik's group

25 minutes ago

47 minutes ago

56 minutes ago

### jkju

1 hour ago
Mani Siddiqui posted a status
"Life is a gamE uhh caN BE a playeR oR a toY"
1 hour ago

1 hour ago

1 hour ago