1
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$$
2
GATE CSE 2015 Set 1
Numerical
+2
-0
GATE CSE 2015 Set 1 Theory of Computation - Finite Automata and Regular Language Question 28 English

Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is___________.

Your input ____
3
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
4
GATE CSE 2014 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_2} = \left\{ {w \in \left\{ {0,\,\,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(000)'s$$ as $$(111)'s$$$$\left. \, \right\}$$. Which one of the following is TRUE?
A
$${L_1}$$ is regular but not $${L_2}$$
B
$${L_2}$$ is regular but not $${L_1}$$
C
Both $${L_1}$$ and $${L_2}$$ are regular
D
Neither $${L_1}$$ nor $${L_2}$$ are regular
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