1
GATE CSE 2008
MCQ (Single Correct Answer)
+1
-0.3
Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?
A
It is not accepted by a Turing machine
B
It is regular but not context-free
C
It is context-free but not regular
D
It is neither regular nor context-free, but accepted by a Turing machine
2
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$$
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 2008
MCQ (Single Correct Answer)
+2
-0.6
Match the following $$NFAs$$ with the regular expressions they correspond to GATE CSE 2008 Theory of Computation - Finite Automata and Regular Language Question 58 English 1 GATE CSE 2008 Theory of Computation - Finite Automata and Regular Language Question 58 English 2 GATE CSE 2008 Theory of Computation - Finite Automata and Regular Language Question 58 English 3 GATE CSE 2008 Theory of Computation - Finite Automata and Regular Language Question 58 English 4 GATE CSE 2008 Theory of Computation - Finite Automata and Regular Language Question 58 English 5
A
$$P - 2,\,Q - 1,\,R - 3,\,S - 4$$
B
$$P - 1,\,Q - 3,\,R - 2,\,S - 4$$
C
$$P - 1,\,Q - 2,\,R - 3,\,S - 4$$
D
$$P - 3,\,Q - 2,\,R - 1,\,S - 4$$
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12