Web Page

$$\small{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Year}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum} \\\hline\textbf{1 Mark Count}&2&2&2&3&3&3&2&2.5&3 \\\hline\textbf{2 Marks Count}&3&3&5&3&3&3&3&3.3&5 \\\hline\textbf{Total Marks}&8&8&12&9&9&9&\bf{8}&\bf{9.2}&\bf{12}\\\hline \end{array}}}$$

# Recent questions in Theory of Computation

1
Which of the following is not a monotonically increasing grammar? (A) Context-sensitive grammar (B) Unrestricted grammar (C) Regular grammar (D) Context-free grammar
2
If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called decidable undecidable interpretive non-deterministic
3
The defining language for developing a formalism in which language definitions can be stated, is called syntactic meta language decidable language intermediate language high level language
4
Regular expression $(a \mid b)(a \mid b)$ denotes the set $\{a,b,ab,aa\}$ $\{a,b,ba,bb\}$ $\{a,b\}$ $\{aa,ab,ba,bb\}$
5
Two finite state machines are said to be equivalent if they have same number of states have same number of edges have same number of states and edges recognize same set of tokens
1 vote
6
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ Only $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only
7
A language $L$ for which there exists a $TM\;\;’T’,$ that accepts every word in $L$ and either rejects or loops for every word that is not in $L,$ is said to be Recursive Recursively enumerable NP-HARD None of the above
1 vote
8
The logic of pumping lemma is a good example of the pigeon-hole principle the divide and conquer technique recursion iteration
9
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only
10
Choose the correct statements. A total recursive function is also a partial recursive function A partial recursive function is also a total recursive function A partial recursive function is also a primitive recursive function None of the above
1 vote
11
The automaton which allows transformation to a new state without consuming any input symbols : $NFA$ $DFA$ $NFA - 1$ All of the options
12
Complement of a $DFA$ can be obtained by : making starting state as final state. make final as a starting state. making final states non-final and non-final as final. None of the options
13
Concatenation Operation refers to which of the following set operations : Union Dot Kleene None of the options
14
Which of the following statements is true ? Melay and Moore machines are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
15
If $L1$ and $L2$ are regular sets then intersection of these two will be : Regular Non Regular Recursive Non Recursive
16
Let $P, Q, R$ be a regular expression over $\Sigma$. If $P$ does not contain null string, then $R=Q+RP$ has a unique solution ___________ . $Q^{*}P$ $QP^{*}$ $Q^{*}P^{*}$ $\left ( P^{*}O^{*} \right)^{*}$
17
A finite automaton accepts which type of language : Type $0$ Type $1$ Type $2$ Type $3$
1 vote
$\left (0+ \varepsilon \right) \left (1+ \varepsilon \right)$ represents : $\left \{0,1,01,\varepsilon \right \}$ $\left \{0,1,\varepsilon \right \}$ $\left \{0,1,01, 11, 00 ,10,\varepsilon \right \}$ $\left \{0,1, \right \}$
What is the relation between $DFA$ and $NFA$ on the basis of computational power ? $DFA$ > $NFA$ $NFA$ > $DFA$ Equal Can't be said
How many DFA's exits with two states over input alphabet $\left \{ 0,1 \right \}$ $16$ $26$ $32$ $64$