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

Hot questions in Theory of Computation

1 votes
0 answers
6123
TURING MACHINE
Design a Turing Machine that accepts a language L, a*ba*b.
Design a Turing Machine that accepts a language L, a*ba*b.
User Avatar
1 votes
1 answer
6125
gateforum test series
Consider the following DFA: Language accepted by DFA is All the string ending with same symbol All the string containing 10 or 01 as substring All the string where leftmost symbol differs from rightmost symbol (0+1)*(01+10)
Consider the following DFA: Language accepted by DFA isAll the string ending with same symbolAll the string containing 10 or 01 as substringAll the string where leftmost ...
User Avatar
4 votes
1 answer
6127
Pumping Lemma
Prove or Disprove below language is regular or not L1={w|w∈∑* where w visit all state of M atleast once where M is machine accepting L1 L2={w|w∈∑* where w visit all state of M equal no of times where M is machine accepting L2
Prove or Disprove below language is regular or notL1={w|w∈∑* where w visit all state of M atleast once where M is machine accepting L1 L2={w|w∈∑* where ...
User Avatar
1 votes
1 answer
6129
Automata
What is R-L, where R is a regular language and L is context free. Options are a.Regular, b.Context free,c.Context Sensitive ,d.None of this
What is R-L, where R is a regular language and L is context free.Options are a.Regular, b.Context free,c.Context Sensitive ,d.None of this
User Avatar
2 votes
1 answer
6130
Regular expression
Which of the following regular expr. Generate set of all strings not containing 100 as substring. a. 0*(1+0)* b 0*1010* c. 0*1*01 d. 0*(0+1)* I think none of them is correct one Ans should be 0*(1+01)*
Which of the following regular expr. Generate set of all strings not containing 100 as substring.a. 0*(1+0)*b 0*1010*c. 0*1*01d. 0*(0+1)*I think none of them is correct o...
User Avatar
3 votes
1 answer
6131
UGC NET CSE | December 2014 | Part 3 | Question: 62
Match the following $:$ ... $\text{a-iv, b-i, c-ii, d-iii}$ $\text{a-i, b-iv, c-iii, d-ii}$
Match the following $:$ $\begin{array} {clcl} & \textbf{List – I} && \textbf{List – II} \\ \text{a.}& \text{Context free grammar} & \text{i.} & \text{Linear bounded a...
User Avatar
1 votes
1 answer
6132
Turing Machine
State True/False: "A Turing Machine is equivalent to a PDA with two or more stacks."
State True/False:"A Turing Machine is equivalent to a PDA with two or more stacks."
User Avatar
2 votes
0 answers
6133
CONTEXT FREE LANGUAGE
Covert the right-linear grammar to its equivalent left-linear grammar: S -> aA | bB | aS | a A -> bA | є B -> aB | є
Covert the right-linear grammar to its equivalent left-linear grammar:S - aA | bB | aS | aA - bA | є B - aB | є
User Avatar
2 votes
2 answers
6134
self doubt
can we further minimize it.
can we further minimize it.
User Avatar
2 votes
1 answer
6136
ISRO2014-59
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input? it may halt and accept the input it may halt by changing the input it may halt and reject the input it may never halt
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?it may halt and accept the inputit may halt by changing...
User Avatar
3 votes
3 answers
6137
Identify the language
L= {(xy)^m (yz)^m | m>=1} identify the language...
L= {(xy)^m (yz)^m | m>=1} identify the language...
User Avatar
1 votes
0 answers
6138
Turing Machine
Desgin a Turing Machine that accept the language L, a*baa*
Desgin a Turing Machine that accept the language L, a*baa*
User Avatar
1 votes
1 answer
6140
UGC NET CSE | June 2014 | Part 2 | Question: 09
The context free grammar for the language $L= \left\{a^{n}b^{m}c^{k} \mid k = \mid n - m\mid , n \geq 0, m \geq 0, k \geq 0\right\}$ ...
The context free grammar for the language $L= \left\{a^{n}b^{m}c^{k} \mid k = \mid n - m\mid , n \geq 0, m \geq 0, k \geq 0\right\}$ is $S \rightarrow S_{1}S_{3}, S_{1} \...
User Avatar
Page: