Regular expressions and finite automata, Context-free grammars and push-down automata, Regular and context-free languages, Pumping lemma, Turing machines and undecidability.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}& \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\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&3&3&2&2&2&3&3&3&2&2.5&3
\\\hline\textbf{2 Marks Count} & 3 &3&4&3&3&3&5&3&3&3&3&3.3&5
\\\hline\textbf{Total Marks} & 8 &8&11&9&8&8&12&9&9&9&\bf{8}&\bf{9.1}&\bf{12}\\\hline
\end{array}}}$$

Previous GATE Questions in Theory of Computation

33 votes

6 answers

241

GATE CSE 1991 | Question: 03,xiii
Let $r=1(1+0)^*, s=11^*0 \text{ and } t=1^*0 $ be three regular expressions. Which one of the following is true? $L(s) \subseteq L(r)$ and $L(s) \subseteq L(t)$ $L(r) \subseteq L(s)$ and $L(s) \subseteq L(t)$ $L(s) \subseteq L(t)$ and $L(s) \subseteq L(r)$ $L(t) \subseteq L(s)$ and $L(s) \subseteq L(r)$ None of the above

Let $r=1(1+0)^*, s=11^*0 \text{ and } t=1^*0 $ be three regular expressions. Which one of the following is true?$L(s) \subseteq L(r)$ and $L(s) \subseteq L(t)$$L(r) \subs...

Kathleen

11.6k views

Kathleen asked Sep 12, 2014

34 votes

2 answers

242

GATE CSE 2008 | Question: 53
Which of the following are regular sets? $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$ $\left\{a^nb^m \mid n =2m \right\}$ $\left\{a^nb^m \mid n \neq m \right\}$ $\left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\}$ I and IV only I and III only I only IV only

Which of the following are regular sets?$\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$$\left\{a^nb^m \mid n =2m \right\}$$\left\{a^nb^m \mid n \neq m \right\}$$\lef...

Kathleen

9.6k views

Kathleen asked Sep 12, 2014

50 votes

11 answers

243

GATE CSE 2008 | Question: 52
Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$ $\epsilon + 0\left(10^*1+00\right)^*0$ $\epsilon + 0\left(10^*1+10\right)^*1$ $\epsilon + 0\left(10^*1+10\right)^*10^*$ $P-2, Q-1, R-3, S-4$ $P-1, Q-3, R-2, S-4$ $P-1, Q-2, R-3, S-4$ $P-3, Q-2, R-1, S-4$

Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$$\epsilon + 0\left(10^*1+00\right)^*0$$\epsilon...

Kathleen

12.7k views

Kathleen asked Sep 12, 2014

66 votes

4 answers

244

GATE CSE 2008 | Question: 51
Match the following: $\small{\begin{array}{|ll|ll|}\hline \text{E.} & \text{Checking that identifiers are declared before their use} & \text{P.} & \text{$L \: = \: \left\{a^nb^mc^nd^m \mid n\: \geq1, m \geq 1\right\}$} \\\hline \text{F.} & \text{Number of formal ... $\text{E-R, F-P, G-Q, H-S}$ $\text{E-P, F-R, G-S, H-Q}$

Match the following:$$\small{\begin{array}{|ll|ll|}\hline \text{E.} & \text{Checking that identifiers are declared before their use} & \text{P.} & \text{$L \: = \: \lef...

Kathleen

14.1k views

Kathleen asked Sep 12, 2014

67 votes

4 answers

245

GATE CSE 2008 | Question: 49
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ ...

Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ indicates a final state)$$\overset{Y}{\begin{array}{|l|l|l|}\hline \text{} & ...

Kathleen

14.7k views

Kathleen asked Sep 12, 2014

27 votes

5 answers

246

GATE CSE 2008 | Question: 48
Which of the following statements is false? Every NFA can be converted to an equivalent DFA Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine Every regular language is also a context-free language Every subset of a recursively enumerable set is recursive

Which of the following statements is false?Every NFA can be converted to an equivalent DFAEvery non-deterministic Turing machine can be converted to an equivalent determi...

Kathleen

8.7k views

Kathleen asked Sep 12, 2014

33 votes

5 answers

247

GATE CSE 2008 | Question: 13, ISRO2016-36
If $L$ and $\overline{L}$ are recursively enumerable then $L$ is regular context-free context-sensitive recursive

If $L$ and $\overline{L}$ are recursively enumerable then $L$ isregularcontext-freecontext-sensitiverecursive

Kathleen

11.6k views

Kathleen asked Sep 11, 2014

48 votes

3 answers

248

GATE CSE 2008 | Question: 10
Which of the following are decidable? Whether the intersection of two regular languages is infinite Whether a given context-free language is regular Whether two push-down automata accept the same language Whether a given grammar is context-free I and II I and IV II and III II and IV

Which of the following are decidable?Whether the intersection of two regular languages is infiniteWhether a given context-free language is regularWhether two push-down au...

Kathleen

13.6k views

Kathleen asked Sep 11, 2014

29 votes

3 answers

249

GATE CSE 2008 | Question: 9
Which of the following is true for the language $\left\{ a^p \mid p \text{ is a prime } \right \}?$ It is not accepted by a Turing Machine It is regular but not context-free It is context-free but not regular It is neither regular nor context-free, but accepted by a Turing machine

Which of the following is true for the language$$\left\{ a^p \mid p \text{ is a prime } \right \}?$$It is not accepted by a Turing MachineIt is regular but not context-fr...

Kathleen

8.2k views

Kathleen asked Sep 11, 2014

57 votes

1 answer

250

GATE CSE 1999 | Question: 1.6
Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true? $L_1 = L_2$ $L_1 \supset L_2$ $L_1 \subset L_2$ None

Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true?$L_1 = L...

Keith Kr

22.0k views

Keith Kr asked Sep 10, 2014

45 votes

3 answers

251

GATE CSE 2003 | Question: 52
Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* \to \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial ... $\in NP$ and $L_2$ $\in P$ $L_1$ is undecidable and $L_2$ is decidable $L_1$ is recursively enumerable and $L_2$ is recursive

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* \to \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x...

Arjun

8.5k views

Arjun asked Sep 8, 2014

70 votes

4 answers

252

GATE CSE 2003 | Question: 54
Define languages $L_0$ and $L_1$ as follows : $L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\} $ $L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts on }w\}$ Here $\langle M, w, i \rangle$ is a ... $L'$ is recursively enumerable, but $ L$ is not Both $L$ and $L'$ are recursive Neither $L$ nor $L'$ is recursively enumerable

Define languages $L_0$ and $L_1$ as follows :$L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\} $$L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts o...

Arjun

24.1k views

Arjun asked Sep 8, 2014

57 votes

4 answers

253

GATE CSE 2003 | Question: 15
If the strings of a language $L$ can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true? $L$ is necessarily finite $L$ is regular but not necessarily finite $L$ is context free but not necessarily regular $L$ is recursive but not necessarily context-free

If the strings of a language $L$ can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?$L$ is necessarily fin...

gauravsachan9188

15.6k views

gauravsachan9188 asked Aug 24, 2014

71 votes

14 answers

254

GATE CSE 2012 | Question: 12
What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$

What is the complement of the language accepted by the NFA shown below?Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.$\phi$$\{\epsilon\}$$a^*$$\{a , \epsilon...

gatecse

19.3k views

gatecse asked Aug 5, 2014

23 votes

4 answers

255

GATE CSE 2012 | Question: 4
Assuming $P \neq NP$, which of the following is TRUE? $NP- \ complete = NP$ $NP-complete \cap P = \phi$ $NP-hard = NP$ $P = NP-complete$

Assuming $P \neq NP$, which of the following is TRUE?$NP- \ complete = NP$$NP-complete \cap P = \phi$$NP-hard = NP$$P = NP-complete$

gatecse

9.0k views

gatecse asked Aug 5, 2014

Page:

« prev
1
...
8
9
10
11
12
13

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true