1
GATE CSE 2016 Set 1
+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.$$ 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
+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: 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 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___________.

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 ________________.
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization
EXAM MAP
Joint Entrance Examination