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

Most answered questions in Theory of Computation

2 votes
4 answers
182
Decidability
The problem described by the language $L = \left\{ \langle M_1,M_2 \rangle \mid L(M_1) = L(M_2) \right\}$ is a) Decidable b) Semi decidable c) not even semi-decidable
The problem described by the language $L = \left\{ \langle M_1,M_2 \rangle \mid L(M_1) = L(M_2) \right\}$ isa) Decidable b) Semi decidable c) not even semi-decidable
User Avatar
7 votes
4 answers
184
TOC SAMPLE PRACTICE
Determine the minimum height of parse tree in CNF for terminal string of length w, which is constructed by using CFG G (a) log2|w|+1 (b) log2|w| (c) log2|w|−1 (d) None of these
Determine the minimum height of parse tree in CNF for terminal string of length w, which is constructed by using CFG G(a) log2|w|+1 (b) log2|w|(c) log2|w|−1 (d) None of...
User Avatar
0 votes
4 answers
186
minimal DFA
construct the minimal DFA for the language L={ 3rd symbol from the R.H.S is 'a'} and ∈={a.b}.
construct the minimal DFA for the language L={ 3rd symbol from the R.H.S is 'a'} and ∈={a.b}.
User Avatar
2 votes
4 answers
187
#TOC what will be the R.E of this DFA?
I'm getting R.E as 0*1(01)*1(0+1)* but people are getting (0+10)*11(1+0)* Please tell, how!?
I'm getting R.E as 0*1(01)*1(0+1)* but people are getting (0+10)*11(1+0)*Please tell, how!?
User Avatar
2 votes
4 answers
189
Recursive languages.
If L1 is Recursive language and L2 is RE. Then L1 ⋂ L2 is RE? Since every Recursive language is RE, then how intersection of the Recursive and RE is RE?
If L1 is Recursive language and L2 is RE. Then L1 ⋂ L2 is RE? Since every Recursive language is RE, then how intersection of the Recursive and RE is RE?
User Avatar
5 votes
4 answers
190
The intersection of a context free language  and a regular language 
The intersection of a context free language and a regular language a)need not be regular b)need not be context free c) is always regular d) is always context free
The intersection of a context free language and a regular language a)need not be regularb)need not be context freec) is always regulard) is always context free
User Avatar
0 votes
4 answers
192
RegulaR Expression
Find the regular expression No 2 a's and 2 b's should come together?
Find the regular expression No 2 a's and 2 b's should come together?
User Avatar
1 votes
4 answers
195
GB Mock 2
User Avatar
6 votes
4 answers
197
TOC- DFA
Number of states in DFA which accepts the binary strings divisible by 4 or 5. answer?
Number of states in DFA which accepts the binary strings divisible by 4 or 5.answer?
User Avatar
14 votes
4 answers
199
GATE CSE 1987 | Question: 2l
State whether the following statement are TRUE or FALSE. $A$ is recursive if both $A$ and its complement are accepted by Turing machines.
State whether the following statement are TRUE or FALSE.$A$ is recursive if both $A$ and its complement are accepted by Turing machines.
User Avatar
21 votes
4 answers
200
GATE CSE 1987 | Question: 2k
State whether the following statements are TRUE or FALSE: The intersection of two CFL's is also a CFL.
State whether the following statements are TRUE or FALSE:The intersection of two CFL's is also a CFL.
User Avatar
Page: