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

#4481
375
views
1 answers
1 votes
peter linz excercise
User Avatar
#4482
2.4k
views
1 answers
1 votes
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))?
User Avatar
#4483
2.3k
views
1 answers
0 votes
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}.
User Avatar
#4484
242
views
0 answers
1 votes
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
User Avatar
#4485
530
views
1 answers
0 votes
theory of computation
Consider the following statements.S1 : union of any finite number of countable sets is countable.S2 : union of infinite number of countable sets is countable S3 : cross product of any ... S3)C) Only S1),S2),S3)D) All of S1),S2),S3),S4)
User Avatar
#4486
1.2k
views
2 answers
2 votes
normal forms
why there is need of normal forms in the context free grammer ????????????????? elaborate with example plz.
User Avatar
#4487
333
views
0 answers
0 votes
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 ??
User Avatar
#4488
434
views
1 answers
0 votes
theory of computation
L = { <M,w> / M is a TM,w is a string and M on simulating w,the Read/write head of M moves 100 steps away from the left most symbol of input ... of input. MY ANSWER : This language is Recursively enumerable but not recursive ...right ???
User Avatar
#4489
252
views
0 answers
0 votes
Gate 2017
Please explain why L3 is not CFL?
User Avatar
#4490
431
views
2 answers
0 votes
grammer
S -> Sis a context-free grammar or not?
User Avatar
#4491
389
views
1 answers
0 votes
theory of computation
This language,L = { <M,w> / M is a TM,w is a string and M does not halt on string w }is not recursively enumerable ...right ???
User Avatar
#4492
157
views
0 answers
0 votes
theory of computation
why the above language is not Recursively enumerable ??? please explain
User Avatar
#4493
1.1k
views
2 answers
2 votes
theory of computation
Which of the following languages below are NOT recursively enumerable ?L1 = {<M> / M is a TM that accepts all even numbers }.L2 = {<M> / M does not accept all even ... ) Only L1B) Only L1 and L2C) Only L1 and L3 D) All of L1,L2 and L3
User Avatar
#4494
4.5k
views
3 answers
2 votes
Push Down Automata
Which one is more powerful Deterministic push down automata or Non Deterministic push down automata ?
User Avatar
#4495
455
views
2 answers
1 votes
Peter Linz, 3rd Ed, Chapter 1, Pg 15, Ques 19
if f(n) = O(n2) and g(n) = O(n3), thenwhat is the complexity of f(n)*g(n) and f(n)/g(n) in big-o-notation?
User Avatar
#4496
2.6k
views
3 answers
4 votes
TOC: empty language and epsilon
What is ∅ U ∅* ?a) ∅b) ϵc) Both a and b can be answerd) Neither a nor b
User Avatar
#4497
763
views
1 answers
0 votes
theory of computation
can a turing machine accept $\varepsilon$ ??? please explain ??? this question says it can accept ...https://gateoverflow.in/941/gate2003-53
User Avatar
#4498
1.7k
views
2 answers
1 votes
regular expression
1(01)* and (10)*1, are both regular expressions are equal?i think not, as 10 can be accepted by first regular expression, but it cannot be accepted by the ... always ends with 1.Is it correct? Please correct me if iam wrong. Thank You.
User Avatar
#4499
675
views
2 answers
1 votes
Check for Regular Language
Check whether given language is Regular or not?WXWR / W,X∈(0,1)+
User Avatar
#4500
276
views
1 answers
0 votes
theory of computation
Answer is [[n(n+1)] / 2 ] + 1 right ??? empty string is also a substring right ???
User Avatar
Page: