targate 2262

Enter "Paper ID, Question Number" in subject line for query! Start a new thread for every question.

Moderators: karthrags, arun_kumar, CS Moderators Team

targate 2262

Postby amitmandal03 » Sun Feb 03, 2013 3:24 pm

Q NO 28 : L(P) accepts nothing ???? isn't answer D ?
Q NO 43 : Both option A and C is correct.. ??
~Amit
User avatar
amitmandal03
Gatementor Guru
Gatementor Guru
 
Posts: 1539
Joined: Sat Sep 22, 2012 3:19 pm
Currently what are you doing?: Am Studying
My College/Company:: GATE
Roll Number: 0
City: Bangalore

Re: targate 2262

Postby positivemind » Sun Feb 03, 2013 4:34 pm

agree with Q43 both A,C are valid traversals.
Q49 Is no of spanning trees = 3 ? edge ac (cost 14) will always be included so only 'be' and 'ed' can form spanning trees?
positivemind
 
Posts: 74
Joined: Mon Sep 17, 2012 10:09 pm
My College/Company:: gateforum
Roll Number: 12345678

Re: targate 2262

Postby amitmandal03 » Sun Feb 03, 2013 8:28 pm

positivemind wrote:agree with Q43 both A,C are valid traversals.
Q49 Is no of spanning trees = 3 ? edge ac (cost 14) will always be included so only 'be' and 'ed' can form spanning trees?

ac ,be ,ed are of same cost .. so any two can be used.... [why ac will be fixed ?? ]
total spanning tree is 3C2 =3
~Amit
User avatar
amitmandal03
Gatementor Guru
Gatementor Guru
 
Posts: 1539
Joined: Sat Sep 22, 2012 3:19 pm
Currently what are you doing?: Am Studying
My College/Company:: GATE
Roll Number: 0
City: Bangalore

Re: targate 2262

Postby positivemind » Sun Feb 03, 2013 11:36 pm

yes got it thanks.

Q28 Why L(P) is empty ? its NPDA accepting even palindromes.
positivemind
 
Posts: 74
Joined: Mon Sep 17, 2012 10:09 pm
My College/Company:: gateforum
Roll Number: 12345678

Re: targate 2262

Postby amitmandal03 » Mon Feb 04, 2013 1:01 am

consider string 0110(even length palimdrome] I am using d as delta
d(q0,0,Z0) ->[q0,RZ0] stack content [Z0,R,---------]
d(q0,1,R) ->[q0,TR] stack content [Z0,R,T---------]
d(q0,1,T) -> [q0,TT] stack content [Z0,R,T,T---------]
d(q0,0,T) ->[q0,RT] stack content [Z0,R,T,T,R---------]
d(q0,epsilon,R)->[q1,R] stack content [Z0,R,T,T,R---------]

now input is epsilon and we have no transition defined for epsilon when in state q1 and syMbols other than Z0 and .. so how are you accepting string ??? and how are you reaching final state ?
~Amit
User avatar
amitmandal03
Gatementor Guru
Gatementor Guru
 
Posts: 1539
Joined: Sat Sep 22, 2012 3:19 pm
Currently what are you doing?: Am Studying
My College/Company:: GATE
Roll Number: 0
City: Bangalore

Re: targate 2262

Postby MonikaD » Mon Feb 04, 2013 10:20 am

How was the paper guys? Was it up to standards??
MonikaD
Gatementor Resident
Gatementor Resident
 
Posts: 353
Joined: Mon Jul 16, 2012 12:18 am
Currently what are you doing?: Am Studying
My College/Company:: IISC Bangalore
Roll Number: 0
City: Mumbai

Re: targate 2262

Postby amitmandal03 » Mon Feb 04, 2013 1:33 pm

MonikaD wrote:How was the paper guys? Was it up to standards??

no way ! Gate is not going to ask direct questions.. i was expecting better level but again they repeated same old questions.
~Amit
User avatar
amitmandal03
Gatementor Guru
Gatementor Guru
 
Posts: 1539
Joined: Sat Sep 22, 2012 3:19 pm
Currently what are you doing?: Am Studying
My College/Company:: GATE
Roll Number: 0
City: Bangalore

Re: targate 2262

Postby sriram08 » Mon Feb 04, 2013 2:36 pm

@amit regarding q28
Logic of this transition is after every input scanned, a symbol is pushed and will try to pop the stack to check for palindrome.
ephsilon transition will be happening after every step .
example 0110 i have scanned 0 pushed R as well as pop R(bcoz of ephislon) .but the scenario in which i pop R will end in the next two transition as i don't have d(q1,1,Z0)
In a case where i m starting to pop characters after 01 i would reach final state.

It won't work for odd palindromes because in that case when i reach the middle i need to move right to q1 without doing anything and after that start popping.
Adding below 4 transition will make it work for all strings
d(q0,0,R) = [q1,R]
d(q0,0,T) = [q1,T]
d(q0,1,R) = [q1,R]
d(q0,1,T) = [q1,T]
sriram08
 
Posts: 5
Joined: Mon Feb 04, 2013 2:11 pm
My College/Company:: Tcs
Roll Number: 28125158

Re: targate 2262

Postby amitmandal03 » Mon Feb 04, 2013 2:44 pm

sriram08 wrote:@amit regarding q28
Logic of this transition is after every input scanned, a symbol is pushed and will try to pop the stack to check for palindrome.
ephsilon transition will be happening after every step .

where is this mentioned that "ephsilon transition will be happening after every step" you cannot build your own logic . we have to go according to transaction defined
GATEFORUM is smart enough to hide their mistakes. that's why they havn't given video explanation for q28.
~Amit
User avatar
amitmandal03
Gatementor Guru
Gatementor Guru
 
Posts: 1539
Joined: Sat Sep 22, 2012 3:19 pm
Currently what are you doing?: Am Studying
My College/Company:: GATE
Roll Number: 0
City: Bangalore

Re: targate 2262

Postby sriram08 » Mon Feb 04, 2013 2:54 pm

amitmandal03 wrote:
sriram08 wrote:@amit regarding q28
Logic of this transition is after every input scanned, a symbol is pushed and will try to pop the stack to check for palindrome.
ephsilon transition will be happening after every step .

where is this mentioned that "ephsilon transition will be happening after every step" you cannot build your own logic . we have to go according to transaction defined
GATEFORUM is smart enough to hide their mistakes. that's why they havn't given video explanation for q28.


what do you mean by ephsilon transition?...what do u do in NFA ...?
i can have any number of ephsilons in my input string...0110 is same as [01 ephsilon 10]
sriram08
 
Posts: 5
Joined: Mon Feb 04, 2013 2:11 pm
My College/Company:: Tcs
Roll Number: 28125158

Next

Return to CS Paper Question

Who is online

Users browsing this forum: No registered users and 1 guest
cron