The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged theoryofcomputation
Webpage for Theory of Computation:
0
votes
1
answer
1
Self Doubt
L= { M⟩L(M) accepts empty string} L={⟨M⟩TM halts on empty string} Identify RE , REC , Not RE ?? Are this two languages or same I think both are same if TM halts on $\epsilon$ then L(M) accepts $\epsilon$ right ??
asked
18 hours
ago
in
Theory of Computation
by
jatin khachane 1
Active
(
3k
points)

15
views
theoryofcomputation
decidability
0
votes
0
answers
2
Halting problem of TM which recognize recursive languages is undecidable?
asked
20 hours
ago
in
Theory of Computation
by
gmrishikumar
(
451
points)

19
views
decidability
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
turingmachine
ricetheorem
0
votes
0
answers
3
Madeeasy
Options: $\left \{ \left ( b^{n}ab^{n}a\right )^{m}  n,m \geq 0 \right \}$ $\left \{ \left ( b^{n}ab^{n}a\right )^{m}  n,m \geq 0 \right \} \cup \left \{ b^{n}  n\geq 0 \right \}$ $\left \{ \left ( b^{n}ab^{n}\right )^{m}a  n,m \geq 0 \right \}$ $NONE$
asked
1 day
ago
in
Theory of Computation
by
jatin khachane 1
Active
(
3k
points)

73
views
madeeasytestseries
theoryofcomputation
0
votes
0
answers
4
pda doubt
Consider the following PDA: The language accepted by the given PDA is: L = {(b^n a b^n a )^m  m, n >= 0} L = {b^n a b^n a  n >= 0} {bn  n >= 0} L = {b^n a b^n a  n >= 0} L = {(b^n a b^n a )^m  m, n >= 0} {bn  n >= 0}
asked
1 day
ago
in
Theory of Computation
by
Satbir
Active
(
1.1k
points)

17
views
pushdownautomata
theoryofcomputation
0
votes
0
answers
5
Reversal of DFA doubt
in reversal of DFA if there are more than one final states then which one will be made the initial state? a DFA can have only one initial state
asked
1 day
ago
in
Theory of Computation
by
aditi19
Active
(
2k
points)

29
views
theoryofcomputation
finiteautomata
#dfa
minimalstateautomata
0
votes
1
answer
6
ME Test Series
asked
1 day
ago
in
Theory of Computation
by
Shadan Karim
(
233
points)

22
views
theoryofcomputation
0
votes
1
answer
7
Self Doubt
Equal Or Not $\Sigma ^{+} = L . L^{*} ?$
asked
1 day
ago
in
Theory of Computation
by
jatin khachane 1
Active
(
3k
points)

40
views
theoryofcomputation
0
votes
0
answers
8
THEORY OF COMPUTATION
Let $L_1= (0+1)^* , L_2=(01^*0 +1^*) \text{ and } L3=(01^+0 +1^+ + \epsilon) $. If $L=L_1 \cap L_2 \cap L_3$ Then find the number of strings in $L$ which do not contain $11$.
asked
1 day
ago
in
Theory of Computation
by
ROHIT SHARMA 5
(
137
points)

27
views
theoryofcomputation
regularlanguages
0
votes
0
answers
9
proving a language is regular based on two regular language over same $\Sigma$ (complicated)
asked
2 days
ago
in
Theory of Computation
by
csenoob
(
21
points)

5
views
regularlanguages
theoryofcomputation
finiteautomata
closureproperty
0
votes
0
answers
10
VirtualGate CFL or Regular language Identification
asked
2 days
ago
in
Theory of Computation
by
!KARAN
Junior
(
887
points)

30
views
theoryofcomputation
identifyclasslanguage
0
votes
0
answers
11
Grammer
Which of the following problem is undecidable? A) membership problem for CFL B) membership problem for regular language C)membership problem for csl D)membership problem for type O language
asked
3 days
ago
in
Theory of Computation
by
Shivshankar
(
41
points)

32
views
theoryofcomputation
grammar
0
votes
0
answers
12
madeeasy tst series
I THING THERE IS MISTAKE BECAUSE BRACKET ARE CLOSING AFTER ELEMENT E SO ALL OPERATORS HOULD BE POPED AND AND ACCORDING TO ME ANWER SHOLD BE 2… TRY AND CORRECT IF I M WRONG !!!! THANKS IN ADVANCE!!!
asked
3 days
ago
in
Programming
by
CHïntän ÞäTël
(
203
points)

19
views
madeeasytestseries
#data
structure#
acetestseries
theoryofcomputation
databases
programminginc
0
votes
0
answers
13
finding equivalence classes $R_L$ of given languages and separating words
asked
3 days
ago
in
Theory of Computation
by
csenoob
(
21
points)

11
views
finiteautomata
equivalenceclasses
myhillnerode
theoryofcomputation
0
votes
0
answers
14
DFA NFA and ambiguity
Why is Regular grammar obtained from DFA always unambiguous? Why Regular grammar obtained from NFA may or may not be ambiguous?
asked
3 days
ago
in
Theory of Computation
by
OneZero
(
251
points)

4
views
theoryofcomputation
nfa
ambiguous
+1
vote
0
answers
15
Undecidability with PCP
Where can we apply PCP to check, if the grammar is undecidable? Some examples of such grammars Ambiguous grammar Any other example and how they solved with PCP?
asked
4 days
ago
in
Theory of Computation
by
srestha
Veteran
(
103k
points)

31
views
theoryofcomputation
decidability
0
votes
0
answers
16
Extended transition function doubt
α (q1,aba) is {q0, q2} null reachable states are {q0, q1, q2} α (q3,bab) is {q0, q1, q2, q3} none what is extended transition function? and how to solve this kind of question?
asked
4 days
ago
in
Theory of Computation
by
aditi19
Active
(
2k
points)

24
views
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
17
toc nie
L={a$^{2*m}$ b$^{4*n}$ c$^{n}$ d$^{m}$ m,n>=0} L={xwxw$^{r}$x,w $\epsilon$ {0,1}} machine
asked
5 days
ago
in
Theory of Computation
by
amit166
Junior
(
517
points)

87
views
theoryofcomputation
0
votes
0
answers
18
going from equivalnce classes into a DFA
asked
5 days
ago
in
Theory of Computation
by
csenoob
(
21
points)

66
views
#dfa
finiteautomata
theoryofcomputation
compilerdesign
regularlanguages
0
votes
0
answers
19
Self doubt
One general doubt for minimum number of states in DFA. As explained here https://gateoverflow.in/2144/gate201142 If they are asking for minimum states in FA then we will consider min{dfs's, nfa's states} and include dead state in dfa but as we can see in ... we have not considered any dead state. Is it because it will lead to non final state itself? is that a reason or anything else?
asked
5 days
ago
in
Theory of Computation
by
S Ram
Active
(
1.5k
points)

24
views
theoryofcomputation
0
votes
0
answers
20
Self Doubt
Is set difference operation is closed for two CFLs say L1 and L2? Please justify your answer.
asked
6 days
ago
in
Theory of Computation
by
S Ram
Active
(
1.5k
points)

33
views
theoryofcomputation
0
votes
0
answers
21
NIELIT Qtn
Consider the following possible outcomes of executing a Turing machine over a given input. Which of the following outcome is NOT possible? A)TM halts and accepts the input B)TM halts and rejects the input C)TM hangs and accepts the input D)TM never halts.
asked
Dec 2
in
Theory of Computation
by
pps121
Active
(
1.4k
points)

35
views
turingmachine
theoryofcomputation
0
votes
1
answer
22
Madeeasy Test Series
$\Sigma ^{*}  {\left \{ \epsilon \right \}} = \Sigma ^{+} $ $L^{*}  {\left \{ \epsilon \right \}} = L^{+}$ Which of the above is always true ?
asked
Dec 2
in
Theory of Computation
by
jatin khachane 1
Active
(
3k
points)

81
views
theoryofcomputation
madeeasytestseries
0
votes
1
answer
23
self doubt
what is difference between S1 and S2 S1:Any language L over an alphabet Σ,L^+=L{ϵ} is always TRUE. S2: Any language L over an alphabet Σ,L+=L^*{ϵ} is always TRUE. S3:The language L = {$a^nb^k$ :  n – k  = 2} is not regular Which of the following statements is/are correct?
asked
Dec 2
in
Theory of Computation
by
Prince Sindhiya
Active
(
5.2k
points)

31
views
theoryofcomputation
0
votes
0
answers
24
TOC: Regular v/s Not Regular
In the following question, Neither L1 is subset of L2, nor L2 is subset of L1, so i think their intersection should be disjoint and L1 INTERSECTION L2, should be phi which is a Regular language, hence, option (A) should be correct. The given solution:
asked
Dec 1
in
Theory of Computation
by
chauhansunil20th
Active
(
1.8k
points)

24
views
theoryofcomputation
regularlanguages
0
votes
0
answers
25
Self doubt about relation between regular and linear grammar
asked
Nov 30
in
Theory of Computation
by
Abbas Ahmad
(
19
points)

13
views
theoryofcomputation
regulargrammar
finiteautomata
0
votes
1
answer
26
Undirected Graph  Hamiltonian Cycle  NP Complete?
asked
Nov 30
in
Algorithms
by
gmrishikumar
(
451
points)

23
views
graphtheory
cycle
theoryofcomputation
pnpnpcnph
grapg
npcomplete
0
votes
0
answers
27
Condition for regular language to be infinite
asked
Nov 30
in
Theory of Computation
by
MiNiPanda
Boss
(
17.2k
points)

74
views
theoryofcomputation
finiteautomata
regularlanguages
0
votes
0
answers
28
TOC  PDA
Consider a push down automata (PDA) below which runs over the input alphabet (a, b). It has the stack alphabet {z0, X}, where z0 is the bottom of stack marker. The set of states of PDA is {q0,q1} where q0 is the start state and rules of the PDA are, (The languare accepted by the grammar is)
asked
Nov 30
in
Theory of Computation
by
rahuljai
(
35
points)

36
views
pushdownautomata
theoryofcomputation
contextfreelanguage
grammar
cfg
+2
votes
1
answer
29
self doubt
L1=$\left \{ a^nb^kn\neq k \right \} and \;L2=\left \{xyx^rx,y\in \left \{ 0,1 \right \}^+ \right \}$ check whether the language given below is dcfl or not? L=$\left \{ x^rx\in L1 \;but \;not\; L2 \right \}$
asked
Nov 28
in
Theory of Computation
by
Prince Sindhiya
Active
(
5.2k
points)

57
views
theoryofcomputation
Page:
1
2
3
4
5
6
...
91
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IIT HYDERABAD M.Tech (RA) 3Years Winter Session Interview experience
INDIAN AIR FORCE
GATE BOOK _ TEST SERIES DOUBT_
Visualizing complex C code
GATE Book Test Series
Follow @csegate
Gatecse
Recent questions tagged theoryofcomputation
Recent Blog Comments
@
44,054
questions
49,578
answers
162,839
comments
65,775
users