The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook 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 posts tagged theoryofcomputation
1
Theory of Computation  GO Classroom
Day Date Contents Slides Assignments 1 Sep 27 Regular Language alphabets, language(set of strings), language class or language family All languages uncountably infinte, set of all languages(Finite, Regular, Context free) are countably infinite, ... finite movement or configuration, all problems of undecidability is due to reverse movement of R/W head of tape.
posted
Oct 6, 2018
in
Theory of Computation
by
Manoja Rajalakshmi A
Loyal
(
9,509
points)

617
views
theoryofcomputation
goclassroom
preparationschedule
2
DECIDABILITY
PLEASE CHECK MY UNDERSTANDING: 1. Halting Problem: a) A turing machine halts after running for exactly k steps on any input This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input. b) A ... (same as above). c) A turing machine replaces the characters on the tape atmost n times on any input SEMIDECIDABLE(same as above).
posted
Sep 14, 2018
in
Theory of Computation
by
Balaji Jegan
Active
(
4,557
points)

1,008
views
theoryofcomputation
3
Rice Theorem
Nice papers with examples: http://drona.csa.iisc.ernet.in/~deepakd/atc2011/tmreductionsrice.pdf http://people.cs.aau.dk/~srba/courses/CC08/riceuk.pdf
posted
Jan 22, 2016
in
Theory of Computation
by
bahirNaik
Active
(
3,279
points)

225
views
ricetheorem
theoryofcomputation
4
Important Questions in Theory of Computation
Important Ones http://gateoverflow.in/questions/automatatheory?sort=featured More Questions http://www.cse.iitm.ac.in/~theory/tcslab/mfcs98page/mfcshtml/assign6/pb9.html Problem Set 1 Problem Set 2
posted
Aug 9, 2015
in
Theory of Computation
by
Arjun
Veteran
(
377,207
points)

5,909
views
theoryofcomputation
importantquestions
gate
gatecse
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
Recent Posts
Decidability Slides
How to Revise?
AAI JE IT results out! Adv no 02/2018
Graph Theory Slides for GATECSE
Generating Function Useful Link
Follow @csegate
Gatecse
Recent Blog Comments
@arjun sir along with this are there any other...
Thanks :)
You don't have to be,I know what you are going...
Thank you sir!
46,786
questions
51,234
answers
176,581
comments
66,585
users