1
GATE CSE 2013
MCQ (Single Correct Answer)
+1
-0.3
Which of the following statements are TRUE?

1. The problem of determining whether there exists a cycle in an undirected graph is in P.

2. The problem of determining whether there exists a cycle in an undirected graph is in NP.

3. If a problem A is NP−Complete, there exists a non-deterministic polynomial time algorithm to solve A.

A
1 , 2 and 3
B
1 and 2 only
C
2 and 3 only
D
1 and 3 only
2
GATE CSE 2013
MCQ (Single Correct Answer)
+1
-0.3
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production ( i.e., of type $$A \to \varepsilon $$ and $$A \to a$$ ) to parse a string with n tokens?
A
$${n \over 2}$$
B
$$n - 1$$
C
$$2n - 1$$
D
$${2^n}$$
3
GATE CSE 2013
MCQ (Single Correct Answer)
+2
-0.6

Consider the following two sets of LR(1) items of an LR(1) grammar.

$$\eqalign{ & X \to c.X,\,c/d\,\,\,\,\,\,\,\,X \to c.X,\$ \cr & X \to .cX,c/d\,\,\,\,\,\,\,\,X \to .cX,\$ \cr & X \to .d,c/d\,\,\,\,\,\,\,\,\,\,\,X \to .d,\$ \cr} $$

Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?

1. Cannot be merged since look aheads are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.

A
1 only
B
2 only
C
1 and 4 only
D
1, 2, 3 and 4
4
GATE CSE 2013
MCQ (Single Correct Answer)
+1
-0.3
The transport layer protocols used for real time multimedia, file transfer, DNS and email, respectively are
A
TCP, UDP, UDP and TCP
B
UDP, TCP, TCP and UDP
C
UDP, TCP, UDP and TCP
D
TCP, UDP, TCP and UDP
EXAM MAP