1
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Match the following List-$${\rm I}$$ with List - $${\rm II}$$

List-$${\rm I}$$
$$E)$$ Checking that identifiers are declared before their
$$F)$$ Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function
$$G)$$ Arithmetic expression with matched pairs of parentheses
$$H)$$ Palindromes

List-$${\rm II}$$
$$P)$$ $$L = \left\{ {{a^n}{b^m}{c^n}{d^m}\,|\,n \ge 1,m \ge 1} \right\}$$
$$Q)$$ $$X \to XbX\,|\,XcX\,|\,dXf\,|g$$
$$R)$$ $$L = \left\{ {www\,|\,w \in \left( {a\,|\,b} \right){}^ * } \right\}$$
$$S)$$ $$X \to bXB\,|\,cXc\,|\,\varepsilon $$

A
$$E - P,\,F - R,\,G - Q,\,H - S$$
B
$$E - R,\,F - P,\,G - S,\,H - Q$$
C
$$E - R,\,F - P,\,G - Q,\,H - S$$
D
$$E - P,\,F - R,\,G - S,\,H - Q$$
2
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Which of the following statements are true?
$$1.$$ Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa
$$2.$$ All ε-productions can be removed from any context-free grammar by suitable transformations
$$3.$$ The language generated by a context-free grammar all of whose productions are of the form $$X \to w$$ or $$X \to wY$$ (where, $$w$$ is a string of terminals and $$Y$$ is a non terminal), is always regular
$$4.$$ The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees
A
$$1,2,3$$ and $$4$$
B
$$2, 3$$ and $$4$$ only
C
$$1,3$$ and $$4$$ only
D
$$1,2$$ and $$4$$ only
3
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Which of the following statement is false?
A
Every $$NFA$$ can be converted to an equivalent $$DFA$$
B
Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine.
C
Every regular language is also a context- free language
D
Every subset of a recursively enumerable set is recursive
4
GATE CSE 2007
MCQ (Single Correct Answer)
+2
-0.6
Consider the $$CFG$$ with $$\left\{ {S,A,B} \right\}$$ as the non-terminal alphabet, $$\left\{ {a,b} \right\}$$ as the terminal alphabet, $$S$$ as the start symbol and the following set of production rules: GATE CSE 2007 Theory of Computation - Push Down Automata and Context Free Language Question 36 English

For the correct string of (earlier question) how many derivation trees are there?

A
$$1$$
B
$$2$$
C
$$3$$
D
$$4$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP