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. For hardcopy of previous year questions please see
here
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
self dout
what is the difference between denumerable , enumerable , countable. please explain I confused with this term when i see some theorem "Power set of an infinite set(denumerable ) set is not denumerable." "Let S be an infinite countable set. Then its power set 2s is not countable."
asked
16 hours
ago
in
Theory of Computation
by
pream sagar
Junior
(
573
points)

10
views
0
votes
0
answers
2
TEST SERIES
asked
16 hours
ago
in
Theory of Computation
by
debanjan sarkar
Active
(
4.1k
points)

18
views
testseries
0
votes
0
answers
3
Test Series
What will be the minimum no. of states for DFA for the above NFA? Please explain.
asked
1 day
ago
in
Theory of Computation
by
Subham Nagar
Junior
(
659
points)

29
views
#dfa
minimalstateautomata
0
votes
0
answers
4
TOC Hof Croft
The set of string over alphabet 0's and 1 's such that every pair of adjacent 0's appears before adjacent pair of 1's
asked
1 day
ago
in
Theory of Computation
by
Charan Ananta
(
7
points)

12
views
0
votes
0
answers
5
gateforum
asked
1 day
ago
in
Theory of Computation
by
pream sagar
Junior
(
573
points)

23
views
0
votes
0
answers
6
gateforum
how can we solve such type of question?
asked
1 day
ago
in
Theory of Computation
by
pream sagar
Junior
(
573
points)

20
views
0
votes
0
answers
7
gateforum
asked
1 day
ago
in
Theory of Computation
by
pream sagar
Junior
(
573
points)

11
views
0
votes
0
answers
8
gateforum
asked
1 day
ago
in
Theory of Computation
by
pream sagar
Junior
(
573
points)

4
views
0
votes
0
answers
9
gate forum
asked
1 day
ago
in
Theory of Computation
by
pream sagar
Junior
(
573
points)

6
views
+1
vote
0
answers
10
gateforum notebook
which of the following is false? 1) every CFG with useless symbols can be converted into an equivalent grammar with no useless symbols 2) every CFG with ε  production may be converted into an equivalent grammar without ε  productions that generates the same language.
asked
1 day
ago
in
Theory of Computation
by
pream sagar
Junior
(
573
points)

8
views
2
0
votes
0
answers
11
TOC(Grammar)
Ans will be
asked
1 day
ago
in
Theory of Computation
by
minal
Boss
(
15.3k
points)

33
views
0
votes
0
answers
12
Identify Formal Languages
1.L={xwwx,w$\epsilon \left \{ 0,1 \right \}^{\dotplus }$} 2.L={xwwx,w$\epsilon \left \{ 0,1 \right \}^{\star}$} identify formal language
asked
1 day
ago
in
Theory of Computation
by
amit166
(
147
points)

40
views
theoryofcomputation
0
votes
0
answers
13
Doubt
The result of cross product of two DFAs is intersection of two languages or union of the two languages?
asked
2 days
ago
in
Theory of Computation
by
aditi19
Junior
(
695
points)

17
views
finiteautomata
0
votes
0
answers
14
undecidability
Writes Non Blank: Given a turing machine T, does it ever writes a nonblank symbol on its tape, when started with a blank tape. how the above problem is solvable? somewhere i got this explanation: Let the machine only writes blank symbol. Then ... is a nontrivial property of turing machine and every non trivial property of turing machine is undecidable, so this is also undecidable.
asked
2 days
ago
in
Theory of Computation
by
aambazinga
Junior
(
957
points)

9
views
theoryofcomputation
decidability
ricetheorem
turingmachine
–1
vote
0
answers
15
self doubts
what is minimum number of state in the NFA accepting the language;{ab 4ubc}?
asked
2 days
ago
in
Theory of Computation
by
altamash
(
31
points)

11
views
0
votes
0
answers
16
self doubt
given the productions can it be converted to automata directly ? A=aBbAb B=aCbB C=aAbCa If so how will you decide final state from the given productions ?
asked
3 days
ago
in
Theory of Computation
by
hitendra singh
(
353
points)

14
views
0
votes
0
answers
17
question
What is partial derivation tree of a grammar? explain with example.
asked
3 days
ago
in
Theory of Computation
by
pream sagar
Junior
(
573
points)

9
views
0
votes
0
answers
18
countability
whether the given sets countable or uncountable? 1. the set of all finite partitions of N 2. the set of all nonincreasing functions from N to N. 3. the set of all nondecreasing functions from N to N. here, N is natural numbers. please give answer with proper explanation, as i already have one word answer for all of the problems above.
asked
3 days
ago
in
Theory of Computation
by
aambazinga
Junior
(
957
points)

18
views
theoryofcomputation
#countableset
0
votes
0
answers
19
Self doubt Pushdown Automata
Is it required to initialize stack symbol in PDA? If yes then does this PDA have valid transitions?
asked
3 days
ago
in
Theory of Computation
by
Mk Utkarsh
Boss
(
16.9k
points)

10
views
pushdownautomata
theoryofcomputation
0
votes
0
answers
20
Theory of computation
What is regular language and does it can accept any string?
asked
3 days
ago
in
Theory of Computation
by
tejas96
(
7
points)

19
views
0
votes
0
answers
21
Context Free Grammer
What is the CFG of the language? L = {anbmckdl  where n+m = k+l and n, m, k, l ≥ 1}
asked
3 days
ago
in
Theory of Computation
by
soura1819
(
7
points)

22
views
0
votes
0
answers
22
Peter Linz Chapter 12.1 Q14
Consider the set of all nstate Turing machines with tape alphabet Γ = {0,1, B}. Give an expression for m(n), the number of distinct Turing machines with this Γ.
asked
4 days
ago
in
Theory of Computation
by
RohitKumarSingh
(
27
points)

9
views
turingmachine
theoryofcomputation
peterlinz
0
votes
0
answers
23
self doubt
what will be the regular expression for above figure?
asked
4 days
ago
in
Theory of Computation
by
hitendra singh
(
353
points)

52
views
–2
votes
0
answers
24
boook
L={an . bn . cm . cn  m,n ≥ 0 } find CFG of corresponding Language
asked
4 days
ago
in
Theory of Computation
by
amit166
(
147
points)

22
views
cfg
0
votes
0
answers
25
Reduction
A is Recursively Enumerable but not recursive and A reduces to B then which of the following can be true? A) B is Recursive B) B is Recursive Enumerable C) B is Not RE D) B is CFL
asked
4 days
ago
in
Theory of Computation
by
Mk Utkarsh
Boss
(
16.9k
points)

26
views
theoryofcomputation
reduction
0
votes
0
answers
26
selfdoubt
if concatenation of two languages $L_1\ and\ L_2(L_1.L_2)$ is regular then what can we say about $L_1\ and\ L_2 $ ?? is there any possibility of $L_1=nonregular\ ,\ L_2=nonregular \ $ ??
asked
5 days
ago
in
Theory of Computation
by
Prateek Raghuvanshi
Loyal
(
5.8k
points)

89
views
regularlanguages
0
votes
0
answers
27
made easy test series
Is there is any good method or procedure to solve this question? or else I have to try by brute force...
asked
5 days
ago
in
Theory of Computation
by
Daniyal89
(
131
points)

10
views
0
votes
0
answers
28
made easy test series
Is there is any good method or procedure to solve this question? or else I have to try by brute force ,,,like try 1st 0,1,2,3... length string
asked
5 days
ago
in
Theory of Computation
by
Daniyal89
(
131
points)

23
views
0
votes
0
answers
29
Context free languages
X belongs to {a,b}* such that n(a)<n(b)<2n(a) is a CFL. Please somebody explain the push and pop sequences of the alphabets on the stack. I'm not being able to visualise, how it is CFL?
asked
5 days
ago
in
Theory of Computation
by
aambazinga
Junior
(
957
points)

8
views
contextfreelanguage
theoryofcomputation
0
votes
0
answers
30
mock test
how can l2 be a recursive language we have two turing machines both can accept one language but it does not imply whether it halts or not
asked
5 days
ago
in
Theory of Computation
by
garimanand
(
169
points)

7
views
madeeasytestseries
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
prashant jha 1
Sanjay Sharma
Keval Dodiya
Tesla!
Surya Dhanraj
hemant910
minal
Vasu sahu
Abhishek Das 1
Bharati1234
sakharam
Recent Posts
AVL Tree Rotation
self doubt
Mutual Exclusion vs. Hold and Wait
kvs pgt
Algorithms GO Classroom
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
[email protected]
post it as question
[email protected]
@Swaraj i got 74.22 %
@sanjay sharma , my gmail id ...
39,717
questions
46,751
answers
140,564
comments
58,409
users