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

1 1 vote
1 1 answer
30
30 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Properties
Let $L_1$ and $L_2$ be regular languages and let $L_3$ be non-regular. Which statements are always true?$L_1=L_2$ iff $L_1\cap\overline{L_2}=\emptyset$ $L_1\cup L_3$ is n...
User Avatar
0 0 votes
1 1 answer
24
24 views
GO Classes DPP | GATE CS | Theory of Computation | De Morgan & NFA
Consider,Statement $1:$ If a language family is closed under union and complement, then it must also be closed under intersection. Statement $2:$ An NFA can be constructe...
User Avatar
0 0 votes
1 1 answer
27
27 views
GO Classes DPP | GATE CS | Theory of Computation | State Complexity
Which statements are true?Every language recognized by an $n$-state DFA can be recognized by an NFA with $n$ states. Every language recognized by an $n$-state NFA can be ...
User Avatar
0 0 votes
1 1 answer
27
27 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Properties
Let $L_1$ be regular where specified. Which of the following languages are guaranteed to be regular?$\{ww\mid w\in{0,1}^*\}$ $\{ww\mid w\in L_1\}$ $\{w\mid ww\in L_1\}$ $...
User Avatar
0 0 votes
1 1 answer
24
24 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Properties
All languages are over $\{0,1\}$. Which statements are true?If $L_1\subseteq L_2$ and $L_2$ is regular, then $L_1$ must be regular. If $L_1$ and $L_2$ are both non-regula...
User Avatar
1 1 vote
1 1 answer
45
45 views
GO Classes DPP | GATE CS | Theory of Computation | CFL Classification
Let $P=\{a^n\mid n\text{ is prime}\}$.Which statements are correct?$P$ is regular. $P$ is CFL but not regular. If $P$ were CFL, then because it is unary, it would have to...
User Avatar
1 1 vote
1 1 answer
38
38 views
GO Classes DPP | GATE CS | Theory of Computation | CFL Classification
Let $\text{COPY}=\{ww\mid w\in\{a,b\}^*\}$ and $\text{NOTCOPY}=\{x\in\{a,b\}^*\mid x\text{ is not of the form }ww\}$.Which statements are correct?$\text{COPY}$ is not CFL...
User Avatar
1 1 vote
1 1 answer
26
26 views
GO Classes DPP | GATE CS | Theory of Computation | CFL Pumping Lemma
Let $B=\{0^n\#0^{2n}\#0^{3n}\mid n\ge0\}$.Which statements are correct for proving $B$ is not CFL using the pumping lemma?Choose $s=0^p\#0^{2p}\#0^{3p}$, where $p$ is the...
User Avatar
1 1 vote
1 1 answer
32
32 views
GO Classes DPP | GATE CS | Theory of Computation | CFL Classification
Let $A=\{w\in\{a,b,c\}^*\mid \#a(w)=\#b(w)=\#c(w)\}$ and let $R=a^*b^*c^*$. Which statements are correct?$R$ is regular. If $A$ were CFL, then $A\cap R$ would be CFL. $A\...
User Avatar
1 1 vote
1 1 answer
28
28 views
GO Classes DPP | GATE CS | Theory of Computation | CFL Classification
Consider the following languages:$L_1=\{w\in\{a,b\}^*\mid \#a(w)=\#b(w)\}$$L_2=\{w\in\{a,b,c\}^*\mid \#a(w)=\#b(w)=\#c(w)\}$$L_3=\{a^m b^n\mid 5m+4n=44,\ m,n\ge0\}$Which ...
User Avatar
1 1 vote
1 1 answer
56
56 views
GO Classes DPP | GATE CS | Theory of Computation | DCFL
Let $L=\{w\in\{a,b\}^*\mid n_a(w)\ne n_b(w)\}$. Which statements are correct?$L$ is regular. $L$ is DCFL. $L$ is not CFL. A DPDA can maintain the current surplus using th...
User Avatar
1 1 vote
1 1 answer
39
39 views
GO Classes DPP | GATE CS | Theory of Computation | DCFL
Let $L_1=\{wcw^R\mid w\in\{a,b\}^*\}$ and $L_2=\{ww^R\mid w\in\{a,b\}^*\}$. Which statements are correct?$L_1$ is a DCFL. $L_2$ is a DCFL. $L_2$ is a CFL. $L_2$ is not ac...
User Avatar
1 1 vote
1 1 answer
37
37 views
GO Classes DPP | GATE CS | Theory of Computation | CFL & DCFL
Let $L=\{a^i b^j c^k\mid i=j\text{ or }j=k,\ i,j,k\ge0\}$. Which statements are correct?$L$ is a CFL. $L$ is a DCFL. $L$ can be written as union of two CFLs: one checking...
User Avatar
1 1 vote
1 1 answer
29
29 views
GO Classes DPP | GATE CS | Theory of Computation | Union of DCFL
Let $L_1=\{a^n b^n\mid n\ge0\}$, $L_2=\{a^n b^{2n}\mid n\ge0\}$, and $L=L_1\cup L_2$.Which statements are correct?$L_1$ is a DCFL. $L_2$ is a DCFL. $L$ is a CFL. $L$ is a...
User Avatar
1 1 vote
1 1 answer
31
31 views
GO Classes DPP | GATE CS | Theory of Computation | DCFL
Let $A=\{a^n b^n\mid n\ge1\}$. Define $L_a=A\cup\{a\}$ and $L_b=A\cup\{b\}$. Which statements are correct?$L_a$ is a DCFL. $L_b$ is a DCFL. Both $L_a$ and $L_b$ are regul...
User Avatar
1 1 vote
1 1 answer
73
73 views
GO Classes DPP | GATE CS | Theory of Computation | Regular vs Non-Regular
Which classification is correct?$\{w\in \{0,1\}^* \mid \#0(w)=\#1(w)\}$ is regular.  $\{w\in \{0,1\}^* \mid \#0(w)=\#1(w)\}$ is not regular.  $\{w\in \{0,1\}^* \mid \#01(...
User Avatar
1 1 vote
1 1 answer
48
48 views
GO Classes DPP | GATE CS | Theory of Computation | Myhill-Nerode
For $L=\{a^n b^n\mid n\ge0\}$, which choice correctly proves non-regularity using Myhill-Nerode?Use $S=\{a^i\mid i\ge0\}$ and distinguish $a^i$ from $a^j$ using suffix $b...
User Avatar
1 1 vote
1 1 answer
47
47 views
GO Classes DPP | GATE CS | Theory of Computation | Regular Language
Let $L=\{w\in{0,1}^*\mid w$ contains equal numbers of substrings $01$ and $10\}$. Which statements are correct?$L$ is regular. A correct regular expression for $L$ is $\e...
User Avatar
1 1 vote
1 1 answer
45
45 views
GO Classes DPP | GATE CS | Theory of Computation | Pumping Lemma
To prove $L=\{a^n b^n\mid n\ge0\}$ is not regular using the pumping lemma, choose $w=a^p b^p$, where $p$ is the pumping length. Which statements are correct?Since $|xy|\l...
User Avatar
1 1 vote
1 1 answer
39
39 views
GO Classes DPP | GATE CS | Theory of Computation | Regular Language
Let $L_n=\{0^n1^n\}$ for each $n\ge0$. Which statements are correct?Each $L_n$ is regular. Any finite union of such languages is regular. $\bigcup_{n\ge0}L_n=\{0^n1^n\mid...
User Avatar
Page: