1
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+2
-0.6
Consider the transition diagram of a $$PDA$$ given below with input alphabet $$\sum {\, = \left\{ {a,b} \right\}} $$ and stack alphabet $$\Gamma = \left\{ {X,Z} \right\}.$$ $$Z$$ is the initial stack symbol. Let $$L$$ denote the language accepted by the $$PDA.$$ GATE CSE 2016 Set 1 Theory of Computation - Finite Automata and Regular Language Question 15 English

Which one of the following is TRUE?

A
$$L = \left\{ {{a^n}{b^n}|n \ge 0} \right\}$$ and is not accepted by any finite automata
B
$$L = \left\{ {{a^n}|n \ge 0} \right\} \cup \left\{ {{a^n}{b^n}|n \ge 0} \right\}$$ and is not accepted by any deterministic $$PDA$$
C
$$L$$ is not accepted by any Turing machine that halts on every input
D
$$L = \left\{ {{a^n}|n \ge 0} \right\} \cup \left\{ {{a^n}{b^n}|n \ge 0} \right\}$$ and is deterministic context-free
2
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 21 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
3
GATE CSE 2015 Set 1
Numerical
+2
-0
GATE CSE 2015 Set 1 Theory of Computation - Finite Automata and Regular Language Question 22 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 ____
4
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 ____
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12