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
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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.
Questions without answers in Theory of Computation
No answer
No selected answer
No upvoted answer
Featured
Previous GATE
Web Page
Regular expressions
and
finite automata,
Contextfree grammars
and
pushdown automata,
Regular
and
contextfree languages,
Pumping lemma,
Turing machines
and
undecidability.
No answer
No selected answer
No upvoted answer
Featured
Previous GATE
0
votes
0
answers
1
Regular Language
asked
Feb 2
in
Theory of Computation
by
vijay_jr
Active
(
1.2k
points)

46
views
theoryofcomputation
regularlanguages
finiteautomata
0
votes
0
answers
2
Test series
If possible , plz explain with state diagram..
asked
Feb 1
in
Theory of Computation
by
Manis
Active
(
1.2k
points)

75
views
+1
vote
0
answers
3
toc ace
asked
Feb 1
in
Theory of Computation
by
dm4006
Active
(
1.1k
points)

33
views
0
votes
0
answers
4
TOC ACE
asked
Feb 1
in
Theory of Computation
by
dm4006
Active
(
1.1k
points)

32
views
theoryofcomputation
+2
votes
0
answers
5
ACE TEST
How to solve such ex? Here anwer is (A)
asked
Feb 1
in
Theory of Computation
by
ankit_thawal
Loyal
(
2.5k
points)

41
views
0
votes
0
answers
6
Test Series
We need to draw DFA for it. and then NFA.? Please tell the approach?
asked
Jan 31
in
Theory of Computation
by
Sahil1994
Active
(
1.3k
points)

31
views
theoryofcomputation
0
votes
0
answers
7
Type of Language
Hi Guys, What is the type of $L_{1}$ and $L_{2}$ ? If they are REC then How could it be proved ?
asked
Jan 31
in
Theory of Computation
by
Chhotu
Veteran
(
14.7k
points)

26
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
8
Turing machine tape moves
The maximum number of moves required by a single tape turing machine to simulate a 5tape turing machine, which has 20 moves is a) 20 b) 50 c) 80 d) 90
asked
Jan 31
in
Theory of Computation
by
madhu_523
(
11
points)

12
views
0
votes
0
answers
9
#Practise Class of Languages
$xwxw^r \ w,x \in (a,b)^*$ $wxw^{r}x \ w,x \in (a,b)^*$
asked
Jan 31
in
Theory of Computation
by
Anjan
Active
(
1.8k
points)

29
views
theoryofcomputation
regularlanguages
0
votes
0
answers
10
ME Test
Please check S2.
asked
Jan 31
in
Theory of Computation
by
neelesh bhakt
Active
(
1.1k
points)

29
views
0
votes
0
answers
11
Turing Machine  Membership Problem
asked
Jan 31
in
Theory of Computation
by
Akash Mishra
Active
(
1.1k
points)

35
views
turingmachine
theoryofcomputation
+1
vote
0
answers
12
Theory of Computation
If the language accepted by a machine is $\{\epsilon,ab,abab,ababab,\ldots\}$ then this language can be represented as: a) $L(M)= \{(ab)^{n}$ ,n $\geq 0\}$ or b) $L(M)= \{(ab)^{*}\}$ Which option is correct?
asked
Jan 31
in
Theory of Computation
by
shraddha priya
Loyal
(
3.3k
points)

30
views
0
votes
0
answers
13
Turing machine
Cant we infer that their complexity remains same
asked
Jan 31
in
Theory of Computation
by
Pawan Kumar 2
Boss
(
5.1k
points)

30
views
turingmachine
0
votes
0
answers
14
Regular Languages
Language {w  ww=www} is regular. How and what is this language?
asked
Jan 31
in
Theory of Computation
by
gauravkc
Loyal
(
4.1k
points)

23
views
theoryofcomputation
regularlanguages
0
votes
0
answers
15
Turing Machine
...................................
asked
Jan 30
in
Theory of Computation
by
Tuhin Dutta
Boss
(
7.8k
points)

64
views
theoryofcomputation
turingmachine
+2
votes
0
answers
16
Testbook Live Test 2
asked
Jan 30
in
Theory of Computation
by
Shailin Shah
(
67
points)

64
views
testbooktestseries
testseries
theoryofcomputation
cfg
+1
vote
0
answers
17
monotonic property
what is rice theorem for monotonic property
asked
Jan 29
in
Theory of Computation
by
raviyogi
Loyal
(
2.6k
points)

24
views
theoryofcomputation
+1
vote
0
answers
18
Theory of Computation
Consider the homomorphism h(a) = 11 amd h(b) = 10. Consider the inverse homomorphism of the regular set (01+00)* a) The resulting set is empty b) The resulting set is 00* c) The resulting set is infinite d) None of the above How to solve this?
asked
Jan 29
in
Theory of Computation
by
gauravkc
Loyal
(
4.1k
points)

31
views
theoryofcomputation
homomorphism
+1
vote
0
answers
19
ACE TEST SERIES
Identify an equivalent nonleft recursive CFG for the following CFG: How to solve such quesitons? I know that, if A>Ax/y then it will be reduced to A>yA' A'>xA'/epsilon How to identify "y" from above example.
asked
Jan 29
in
Theory of Computation
by
ankit_thawal
Loyal
(
2.5k
points)

15
views
+1
vote
0
answers
20
toc dout
here all are non regular grammar how we can identify regular language. if i solve by this way than i think all are regular please correct me if i wrong
asked
Jan 28
in
Theory of Computation
by
ADITYA CHAURASIYA 5
Active
(
1.7k
points)

23
views
+1
vote
0
answers
21
toc doubt
Q. How many total numbers of substrings are possible out of string "abbbccd" 25 27 28 29
asked
Jan 28
in
Theory of Computation
by
Prateek kumar
Veteran
(
10.4k
points)

41
views
theoryofcomputation
+1
vote
0
answers
22
Gate_Model_Paper_TOC
How to find give language is true or not ? please explain it ....step by step
asked
Jan 28
in
Theory of Computation
by
Harikesh Kumar
Active
(
1.7k
points)

29
views
theoryofcomputation
theoryofcomputation
+1
vote
0
answers
23
#testseries
Isn't the second one is CFL?
asked
Jan 28
in
Theory of Computation
by
Sukhdip Singh
(
245
points)

38
views
madeeasytestseries
theoryofcomputation
+2
votes
0
answers
24
How many states in finite automata for the expression L={a^n, where n is a finite number}.
asked
Jan 28
in
Theory of Computation
by
Jayant Isswani
(
41
points)

48
views
finiteautomata
minimalstateautomata
theoryofcomputation
+2
votes
0
answers
25
Decidability
L={R  R is a regular expression, with atleast one w belongs to L(R), i.e. 101 is substring of w} Which one true? a)L is decidable b) L is undecidable c)L is partially decidable
asked
Jan 27
in
Theory of Computation
by
srestha
Veteran
(
81.5k
points)

49
views
decidability
theoryofcomputation
+1
vote
0
answers
26
VIRTUAL GATE  TOC
If $h$ represents the Homomorphic image of a string and $h^{1}$ represent the Inverse Homomorphic image of a string. We have a language $L$, $(A)\ h(h^{1}(L)) = L$ $(B)\ h(h^{1}(L)) \subset L$ $(C)\ h( ... \ None$ Some reference given here, but I am not able to understand: https://courses.engr.illinois.edu/cs373/sp2013/Lectures/lec08.pdf (5th page)
asked
Jan 27
in
Theory of Computation
by
Rishabh Gupta 2
Veteran
(
15.3k
points)

29
views
virtualgate
testseries
theoryofcomputation
homomorphism
+1
vote
0
answers
27
made easy
what will be the resulting lang? I am thinking it as regular although it may clearly seem to be CFL using closure properties, but inclusion of an in the union already take into consideration all strings derived from the CFL part i.e. anbn Hence we can shortcircuit that part? P.S: Answer given is NOT REGULAR
asked
Jan 27
in
Theory of Computation
by
shreyansh jain
Junior
(
733
points)

15
views
+3
votes
0
answers
28
[Ace Test Series] TOC
Can someone please explain me this question ?
asked
Jan 27
in
Theory of Computation
by
ashish pal
Active
(
1.3k
points)

43
views
acetestseries
theoryofcomputation
+1
vote
0
answers
29
Made easy Tests
What is the correct way to solve questions of this kind where equations like these are given and you are asked to determine what languages do the variables X1 X2 X3.. represent?
asked
Jan 27
in
Theory of Computation
by
smriti bhati
(
61
points)

21
views
madeeasytestseries
statediagram
theoryofcomputation
regulargrammar
+1
vote
0
answers
30
ACE test series
(00)*+0(00)*+00(000)* regular expression represents
asked
Jan 26
in
Theory of Computation
by
harshita12
(
23
points)

25
views
To see more, click for the
full list of questions
or
popular tags
.
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
Members at the site
Sourajit25
Veerendra V
smsubham
Anuranjan Chauhan
iarnav
junk_mayavi
itsvkp1
Jeevesh
Digvijay Pandey
Rameshwar Lal
Recent Posts
isro sc 2017 2nd paper
Which college to expect?
Interview Guidance
CDAC CoursesAugust session
Counselling...
All categories
General Aptitude
Engineering Mathematics
Digital Logic
Programming & DS
Algorithms
Theory of Computation
Compiler Design
Operating System
Databases
CO & Architecture
Computer Networks
Non GATE
Others
Admissions
Exam Queries
Tier 1 Placement Questions
Job Queries
Projects
Follow @csegate
Gatecse
Questions without answers in Theory of Computation
Recent Blog Comments
Okay Thanks
i think they call everyone ith a score higher ...
@raviyogi Do you know what was the cutoff ot IIT ...
I think the exam has not yet been created.
Then why it's not appearing as a separate exam in ...
33,707
questions
40,253
answers
114,361
comments
38,874
users