Register

Web Page

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{2024-1} & \textbf{2024-2} & \textbf{2023} & \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} &1&1&3& 2 &2&3& 1&2&3
\\\hline\textbf{2 Marks Count} &2&3&3& 3 &3&4& 2&3&4
\\\hline\textbf{Total Marks} &5&7&9& 8 &8&11&\bf{5}&\bf{8}&\bf{11}\\\hline
\end{array}}}$$

Filter

Highest voted questions in Theory of Computation

#221
10.5k
views
2 answers
24 votes
GATE CSE 2018 | Question: 6
Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true?$k \geq 2^n...
User Avatar
#222
6.0k
views
2 answers
24 votes
Half(L)
If L is Regular Language thenhalf (L) = {u | ∃v : | v | = | u | and uv ∊ L} is also Regular Language.Can anyone plz explain this with simple example.
User Avatar
#223
2.9k
views
2 answers
24 votes
TIFR CSE 2012 | Part B | Question: 19
Which of the following statements is TRUE?Every turning machine recognizable language is recursive.The complement of every recursively enumerable language is recursively ...
User Avatar
#224
15.8k
views
2 answers
24 votes
Inherently ambiguous grammar
Q- Which one of following languages is inherently ambiguous?(A) The set of all strings of the form $\left\{a^nb^n,n>0 \right\}$(B) $\left\{a^nb^nc^md^m,n,m>0 \right\}$(C)...
User Avatar
#225
5.4k
views
1 answers
24 votes
Which of the following languages are Recursively Enumerable language?
Which of the following languages are Recursively Enumerable language?$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which...
User Avatar
#226
6.1k
views
6 answers
24 votes
GATE IT 2006 | Question: 5
Which regular expression best describes the language accepted by the non-deterministic automaton below?$(a + b)^* \ a(a + b)b$$(abb)^*$$(a + b)^* \ a(a + b)^* \ b(a + b)^...
User Avatar
#227
14.8k
views
1 answers
24 votes
GATE CSE 1997 | Question: 20
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$...
User Avatar
#228
7.6k
views
4 answers
24 votes
GATE CSE 2012 | Question: 25
Given the language $L = \left\{ab, aa, baa\right\}$, which of the following strings are in $L^{*}$?$ abaabaaabaa$$ aaaabaaaa$$ baaaaabaaaab$$ baaaaabaa$$\text{1, 2 and 3}...
User Avatar
#229
3.3k
views
1 answers
24 votes
GATE CSE 2002 | Question: 14
The aim of the following question is to prove that the language $\{M \mid M$ $\text {is the code of the Turing Machine which, irrespective of the input, halts and outputs...
User Avatar
#230
15.0k
views
2 answers
24 votes
GATE CSE 2001 | Question: 1.4
Consider the following two statements:$S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language$S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \ri...
User Avatar
#231
8.9k
views
3 answers
23 votes
GATE CSE 2021 Set 2 | Question: 28
Suppose we want to design a synchronous circuit that processes a string of $0$’s and $1$’s. Given a string, it produces another string by replacing the first $1$ in a...
User Avatar
#232
6.6k
views
1 answers
23 votes
GATE IT 2005 | Question: 6
The language $\{0^n 1^n 2^n \mid 1 \leq n \leq 10^6\}$ isregularcontext-free but not regularcontext-free but its complement is not context-freenot context-free
User Avatar
#233
3.9k
views
3 answers
23 votes
GATE IT 2006 | Question: 4
In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string.$S \rightarrow aSa \mid bSb \mid a \mid b \...
User Avatar
#234
4.9k
views
3 answers
23 votes
GATE IT 2006 | Question: 3
In the automaton below, $s$ is the start state and $t$ is the only final state.Consider the strings $u = abbaba, v = bab, \text{and} w = aabb$. Which of the following sta...
User Avatar
#235
8.7k
views
3 answers
23 votes
GATE IT 2008 | Question: 5
Which of the following regular expressions describes the language over$\{0, 1\}$ consisting of strings that contain exactly two $1$'s?$(0 + 1)^ * \ 11(0 + 1) ^*$$0 ^* \ 1...
User Avatar
#236
6.5k
views
6 answers
23 votes
GATE CSE 1996 | Question: 2.8
If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one?$L_1.L_2$$L_1 \cap L...
User Avatar
#237
6.5k
views
3 answers
23 votes
GATE CSE 1998 | Question: 2.6
Which of the following statements is false?Every finite subset of a non-regular set is regularEvery subset of a regular set is regularEvery finite subset of a regular set...
User Avatar
#238
5.0k
views
4 answers
23 votes
GATE CSE 1992 | Question: 02,xix
Context-free languages are:closed under unionclosed under complementationclosed under intersectionclosed under Kleene closure
User Avatar
#239
9.1k
views
4 answers
23 votes
GATE CSE 2012 | Question: 4
Assuming $\textsf{P} \neq \textsf{NP}$, which of the following is TRUE?$\textsf{NP-complete} = \textsf{NP}$$\textsf{NP-complete} \cap \textsf{P} = \phi$$\textsf{NP-hard} ...
User Avatar
#240
5.6k
views
6 answers
22 votes
GATE CSE 1987 | Question: 10d
Give a regular expression over the alphabet $\{0, 1\}$ to denote the set of proper non-null substrings of the string $0110$.
User Avatar
Page: