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

Recent questions in Theory of Computation

0 votes
0 answers
4461
Practice questions
Please provide THE METHOD TO CONSTRUCT DFA for the language For any A⊆Σ*, if A is regular, then so is {x∣xx∊A}
Please provide THE METHOD TO CONSTRUCT DFA for the language For any A⊆Σ*, if A is regular, then so is {x∣xx∊A}
User Avatar
2 votes
4 answers
4462
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
0 votes
3 answers
4463
Finite Automata
User Avatar
0 votes
3 answers
4464
Finite state Machine
which of the following statement is True? a) r* and r+ are always different. b) r* and r+ may be equal. Please explain briefly.
which of the following statement is True?a) r* and r+ are always different. b) r* and r+ may be equal. Please explain briefly.
User Avatar
1 votes
0 answers
4467
peter linz
A leaf labelled (epsilon) has no siblings , i.e. a vertex with a child labelled (epsilon) can have no other children.. please help, unable to get it fully
A leaf labelled (epsilon) has no siblings , i.e. a vertex with a child labelled (epsilon) can have no other children.. please help, unable to get it fully
User Avatar
0 votes
1 answer
4468
Doubt
Is it possible to prove number of b's=2k+1 and any number of a's is regular using Myhill–Nerode theorem ?
Is it possible to prove number of b's=2k+1 and any number of a's is regular using Myhill–Nerode theorem ?
User Avatar
0 votes
2 answers
4469
Finite Automata
How to convert Regular Grammar to Deterministic Finite Automata directly?
How to convert Regular Grammar to Deterministic Finite Automata directly?
User Avatar
0 votes
2 answers
4470
peter linz excercise
Which of the following languages are regular 1)L= wwR v : v,w belongs to {a,b}+ 2)L=uwwR v : u,v,w belongs to {a,b}+ 3)L=uwwR v : u,v,w belongs to {a,b}+ .|u| >= |v|
Which of the following languages are regular1)L= wwR v : v,w belongs to {a,b}+2)L=uwwR v : u,v,w belongs to {a,b}+ 3)L=uwwR v : u,v,w belongs to {a,b}+ .|...
User Avatar
1 votes
1 answer
4471
peter linz excercise
User Avatar
1 votes
1 answer
4472
Peter Linz Question 2.3.6
Is it true that for every nfa M = (Q,Σ,δ,q0,F), the complement of L(M) is equal to the set (a) {w ∈ Σ* : δ*(q0,w) ∩ (Q-F) ≠ Φ)? (b) {w ∈ Σ* : δ*(q0,w) ∈ (Q-F))?
Is it true that for every nfa M = (Q,Σ,δ,q0,F), the complement of L(M) is equal to the set(a) {w ∈ Σ* : δ*(q0,w) ∩ (Q-F) ≠ Φ)?(b) {w ∈ Σ* : δ*(q0,w) ∈ (Q...
User Avatar
0 votes
1 answer
4473
Peter Linz Question 2.2.15
Find an nfa that accepts {a}* and is such that if in its transition graph, a single edge is removed (without any other changes), the resulting automaton accepts {a}.
Find an nfa that accepts {a}* and is such that if in its transition graph, a single edge is removed (without any other changes), the resulting automaton accepts {a}.
User Avatar
1 votes
0 answers
4474
Gate 2008
If L and L’ are recursively enumerable, then L is ( I need detailed explanation why the answer is recursive) (A) regular (B) context-free (C) context-sensitive (D) recursive
If L and L’ are recursively enumerable, then L is( I need detailed explanation why the answer is recursive)(A) regular(B) context-free(C) context-sensitive(D) recursive...
User Avatar
2 votes
2 answers
4476
normal forms
why there is need of normal forms in the context free grammer ????????????????? elaborate with example plz.
why there is need of normal forms in the context free grammer ????????????????? elaborate with example plz.
User Avatar
0 votes
0 answers
4477
theory of computation
L = { <M> / M is a Turing machine and M accepts a regular language }. This Language L is recursively enumerable but not recursive. ...right ??
L = { <M / M is a Turing machine and M accepts a regular language }.This Language L is recursively enumerable but not recursive. ...right ??
User Avatar
0 votes
0 answers
4479
Gate 2017
Please explain why L3 is not CFL ?
Please explain why L3 is not CFL?
User Avatar
Page: