1
GATE CSE 2015 Set 1
MCQ (Single Correct Answer)
+2
-0.6
Consider the NPDA $$\left\langle {Q = \left\{ {{q_0},{q_1},{q_2}} \right\}} \right.,$$ $$\Sigma = \left \{ 0, 1 \right \},$$ $$\Gamma = \left \{ 0, 1, \perp \right \},$$ $$\delta, q_{0}, \perp,$$ $$\left. {F = \left\{ {{q_2}} \right\}} \right\rangle $$ , where (as per usual convention) $$Q$$ is the set of states, $$\Sigma$$ is the input alphabet, $$\Gamma$$ is the stack alphabet, $$\delta $$ is the state transition function q0 is the initial state, $$\perp$$ is the initial stack symbol, and F is the set of accepting states. The state transition is as follows: GATE CSE 2015 Set 1 Theory of Computation - Finite Automata and Regular Language Question 27 English

Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?

A
10110
B
10010
C
01010
D
01001
2
GATE CSE 2015 Set 2
Numerical
+2
-0
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $${\left( {0 + 1} \right)^{\,\, * }}\left( {10} \right)$$ is ________________.
Your input ____
3
GATE CSE 2015 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Which of the following languages is/are regular?

$${L_1}:\left\{ {wx{w^R}|w,x\, \in \left\{ {a,b} \right\}{}^ * } \right.$$ and $$\left. {\left| w \right|,\left| x \right| > 0} \right\},\,{w^R}$$ is the reverse of string $$w$$
$${L_2}:\left\{ {{a^n}{b^m}\left| {m \ne n} \right.} \right.$$ and $$m,n \ge \left. 0 \right\}$$
$${L_3}:\left\{ {{a^p}{b^q}{c^r}\left| {p,q,r \ge 0} \right.} \right\}$$

A
$${L_1}$$ and $${L_3}$$ only
B
$${L_2}$$ only
C
$${L_2}$$ and $${L_3}$$ only
D
$${L_3}$$ only
4
GATE CSE 2015 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Consider the alphabet $$\sum { = \left\{ {0,1} \right\},} $$ the null/empty string $$\lambda $$ and the sets of strings $${X_0},\,{X_1},$$ and $${X_2}$$ generated by the corresponding non-terminals of a regular grammar. $${X_0},\,\,{X_1},\,$$ and $${X_2}$$ are related as follows. $$$\eqalign{ & {X_0} = 1\,X{}_1 \cr & {X_1} = 0{X_1} + 1\,{X_2} \cr & {X_2} = 0\,{X_1} + \left\{ \lambda \right\} \cr} $$$
Which one of the following choices precisely represents the strings in $${X_0}$$?
A
$$10\left( {{0^ * } + {{\left( {10} \right)}^ * }} \right)1$$
B
$$10\left( {{0^ * } + \left( {10} \right){}^ * } \right){}^ * 1$$
C
$$1\left( {0 + 10} \right){}^ * 1$$
D
$$10\left( {0 + 10} \right){}^ * 1 + 110\left( {0 + 10} \right){}^ * 1$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
CBSE
Class 12