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|c|c|c|c|c|c|}\hline \textbf{Year}& \textbf{2026 - 1}& \textbf{2026 - 2}& \textbf{2025 - 1}& \textbf{2025 - 2}& \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}&2&1&2&3&1&1&3&2&2&3&1&2&3\\\hline \textbf{2 Marks Count}&2&2&4&2&2&3&3&3&3&4&2&2.8&4\\\hline \textbf{Total Marks}&6&5&10&7&5&7&9&8&8&11&\bf{5}&\bf{7.6}&\bf{11}\\\hline \end{array}}}$$

Filter

Recent questions in Theory of Computation

0 0 votes
1 1 answer
47
47 views
GO Classes DPP | GATE CS | Theory of Computation | TM Repeated Configuration
Let $M$ be a deterministic Turing machine. During a computation on input $w$, suppose $M$ enters exactly the same complete configuration at two different times before rea...
User Avatar
0 0 votes
1 1 answer
27
27 views
GO Classes DPP | GATE CS | Theory of Computation | TM Infinite Loop
A deterministic Turing machine starts on a blank tape.Which of the following gives an example of a computation that runs forever without ever repeating exactly the same c...
User Avatar
0 0 votes
1 1 answer
25
25 views
GO Classes DPP | GATE CS | Theory of Computation | TM Non-member Behavior
Suppose $M$ recognizes a Turing-recognizable language $A$.Which statement is necessarily true?There must exist some $w\notin A$ on which $M$ loops forever. $M$ must loop ...
User Avatar
1 1 vote
1 1 answer
27
27 views
GO Classes DPP | GATE CS | Theory of Computation | Turing Machine
Let $L$ be any Turing-recognizable language.Which of the following is always possible?Construct a TM that accepts every $w\in L$ and loops forever on every $w\notin L$, n...
User Avatar
0 0 votes
1 1 answer
25
25 views
GO Classes DPP | GATE CS | Theory of Computation | Language of TM
Consider the following deterministic Turing machine $M$ with input alphabet $\Sigma=\{a,b\}$What is $L(M)$?$\{w\in\{a,b\}^*\mid w\text{ ends in }a\}$ $\{w\in\{a,b\}^*\mid...
User Avatar
1 1 vote
1 1 answer
66
66 views
GO Classes DPP | GATE CS | Theory of Computation | TM Recognition Behavior
Let $M$ be a Turing machine that recognizes language $L$, and suppose $w\notin L.$Which of the following behaviors are possible when $M$ is run on $w$?$M$ accepts $w$. $M...
User Avatar
0 0 votes
1 1 answer
41
41 views
GO Classes DPP | GATE CS | Theory of Computation | TM Execution Trace
Consider the following TM strategy for $L=\{b^ic^i\mid i\ge0\}.$It repeatedly:changes the leftmost unmatched $b$ to $\sqcup$ (blank symbol)$,$ scans right to the end of t...
User Avatar
0 0 votes
1 1 answer
37
37 views
GO Classes DPP | GATE CS | Theory of Computation | Turing Machine
Consider $L=\{0^n1^n2^n\mid n\ge0\}.$Which of the following gives a correct high-level strategy for a single-tape Turing machine recognizing $L$?Repeatedly mark the leftm...
User Avatar
0 0 votes
1 1 answer
34
34 views
GO Classes DPP | GATE CS | Theory of Computation | Configuration Transition
Suppose a Turing machine makes the following one-step move:$$011q_7\,00101 \;\vdash\; 0110q_7\,0101.$$What transition must have been used, and what is the next configurat...
User Avatar
1 1 vote
1 1 answer
52
52 views
GO Classes DPP | GATE CS | Theory of Computation | TM Formal Definition
Consider a deterministic single-tape Turing machine$$M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\text{accept}},q_{\text{reject}}).$$Which of the following are required in the stand...
User Avatar
0 0 votes
1 1 answer
51
51 views
GO Classes DPP | GATE CS | Theory of Computation | Infinite Intersection
Let \(I \subseteq \Sigma^*\) be any nonregular language.For every string \(w \notin I\), define $R_w = \Sigma^* - \{w\}.$Now consider $K = \bigcap_{w \notin I} R_w.$What ...
User Avatar
0 0 votes
1 1 answer
48
48 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Property
For every $n\geq 0$, define $L_n=\{a^nb^n\}$.Which statement is correct?Every $L_n$ is nonregular, but $\bigcup_{n=0}^{\infty}L_n$ is regular. Every $L_n$ is regular, and...
User Avatar
0 0 votes
1 1 answer
42
42 views
GO Classes DPP | GATE CS | Theory of Computation | Subset Superset
Let $\Sigma=\{0,1\}.$Which of the following are valid examples?$A=\{01\}, \qquad B=\{0^n1^n\mid n\ge0\}$where $A$ is regular, $B$ is nonregular, and $A\subseteq B$. $C=\{...
User Avatar
0 0 votes
1 1 answer
47
47 views
GO Classes DPP | GATE CS | Theory of Computation | Chomsky Hierarchy
Let $L$ be a context-free language that is not regular.Which of the following must be true?$L$ is recursive. $L$ is not recursive. There exists a regular grammar $G$ such...
User Avatar
0 0 votes
1 1 answer
43
43 views
GO Classes DPP | GATE CS | Theory of Computation | Grammar Classification
Consider the grammar $$S\rightarrow aS\mid Sb\mid b$$ Which of the following statements are correct?The given grammar is a Type $3$ grammar. The given grammar is a Type $...
User Avatar
1 1 vote
1 1 answer
56
56 views
GO Classes DPP | GATE CS | Theory of Computation | Nonregular Union
Suppose $L_1$ and $L_2$ are both nonregular languages.Which statement about $L_1\cup L_2$ is correct?It must be nonregular. It must be regular. It may be regular or nonre...
User Avatar
1 1 vote
1 1 answer
42
42 views
GO Classes DPP | GATE CS | Theory of Computation | Nonregular Reversal
Let $L$ be a nonregular language.What can always be concluded about $L^R$?$L^R$ is regular. $L^R$ is nonregular. $L^R$ may be regular or nonregular. Nothing can be conclu...
User Avatar
1 1 vote
2 2 answers
55
55 views
GO Classes DPP | GATE CS | Theory of Computation | DCFL Reversal
Suppose $L$ is a deterministic context-free language.Which of the following is always correct about$$L^R=\{w^R\mid w\in L\}?$$$L^R$ must be regular. $L^R$ must be determi...
User Avatar
2 2 votes
2 2 answers
83
83 views
GO Classes DPP | GATE CS | Theory of Computation | DCFL Classification
Consider $$L= \{a^ib^jc^k\mid i=j\text{ or }j=k\}.$$ Which of the following correctly classifies $L$?$L$ is regular. $L$ is DCFL but not regular. $L$ is CFL but not DCFL....
User Avatar
1 1 vote
1 1 answer
42
42 views
GO Classes DPP | GATE CS | Theory of Computation | DCFL Closure
Let $L_1,L_2$ be deterministic context-free languages and let $R$ be a regular language.Which of the following statements are always true?$L_1\cup L_2$ is deterministic c...
User Avatar
Page: