The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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 questions tagged nondeterminism
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 3 Question 3 (Page No. 187)
Modify the proof of Theorem $3.16$ to obtain Corollary $3.19$, showing that a language is decidable iff some nondeterministic Turing machine decides it. (You may assume the following theorem about trees. If every node in a ... many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.)
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
51.4k
points)

3
views
michaelsipser
theoryofcomputation
nondeterminism
turingmachine
descriptive
0
votes
0
answers
2
Ullman 2nd edition Theorem 2.22 (Section 2.5)
Here why they are saying we must convert DFA transition into NFA transition?
asked
Mar 3
in
Theory of Computation
by
Bhaskar Singh
(
257
points)

44
views
theoryofcomputation
finiteautomata
nondeterminism
nfa
finiteautomata
+1
vote
1
answer
3
Self Doubt  Confusion on language represented by DFA and NFA
If a DFA "D" have symbol {0,1,2} and NFA "N" have symbol {0,1} but both are representing strings ending with 01 and whole string only contain {0,1} then can we say L(N) = L(D) i.e language represented by DFA is equal to language represented by NFA?
asked
Feb 20
in
Theory of Computation
by
Bhaskar Singh
(
257
points)

68
views
theoryofcomputation
finiteautomata
nfa
nondeterminism
0
votes
0
answers
4
Construct DFA for given Language
For the language which ends with 01 or 11 or 10 or 11 for $\sum$={0,1}* .Is dfa possible for this language?
asked
Oct 16, 2018
in
Theory of Computation
by
sripo
Active
(
2.3k
points)

50
views
minimalstateautomata
theoryofcomputation
finiteautomata
nondeterminism
+1
vote
1
answer
5
Language accepted by given NFA
Language accepted by following NFA and number of states in DFA accepting that Language are: $\{a^nn=2k,kϵN\}$ and 2 $\{a^{2n}n=2k,kϵN\}$ and 2 $\{a^nn=2k,kϵ N\}$ and 3 $\{a^{2n}n=2k,kϵ N\}$ and 3
asked
Mar 2, 2018
in
Theory of Computation
by
GateAspirant999
Active
(
2.4k
points)

104
views
finiteautomata
nondeterminism
theoryofcomputation
+1
vote
0
answers
6
MadeEasy Test Series 2018: Theory of Computation  Non Determinism
isn't the ans is 3 i.e p,q,r
asked
Jan 17, 2018
in
Theory of Computation
by
Sukhdip Singh
(
127
points)

71
views
theoryofcomputation
nondeterminism
madeeasytestseries
madeeasytestseries2018
+1
vote
0
answers
7
#pda #tm #deterministic
How can a DTM can simulate a NTM, but a DPDA can not simulate a NPDA. ? Reason? I read the proedure for a DTM to simulate a NTM but can not get why its not so with pda. Any clue ?
asked
Jul 6, 2017
in
Theory of Computation
by
Shivansh Gupta
Active
(
2.7k
points)

96
views
turingmachine
pushdownautomata
nondeterminism
+14
votes
1
answer
8
GATE2004IT9
Which one of the following statements is FALSE? There exist contextfree languages such that all the contextfree grammars generating them are ambiguous An unambiguous contextfree grammar always has a unique parse tree for each string of the language generated ... automata always accept the same set of languages A finite set of string from some alphabet is always a regular language
asked
Nov 2, 2014
in
Theory of Computation
by
Ishrat Jahan
Boss
(
16.3k
points)

1.3k
views
gate2004it
theoryofcomputation
easy
nondeterminism
+10
votes
3
answers
9
GATE19941.16
Which of the following conversions is not possible (algorithmically)? Regular grammar to context free grammar Nondeterministic FSA to deterministic FSA Nondeterministic PDA to deterministic PDA Nondeterministic Turing machine to deterministic Turing machine
asked
Oct 4, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

893
views
gate1994
theoryofcomputation
easy
nondeterminism
+21
votes
4
answers
10
GATE20118
Which of the following pairs have DIFFERENT expressive power? Deterministic finite automata (DFA) and Nondeterministic finite automata (NFA) Deterministic push down automata (DPDA) and Nondeterministic push down automata (NPDA) Deterministic single tape Turing machine and Nondeterministic single tape Turing machine Single tape Turing machine and multitape Turing machine
asked
Sep 29, 2014
in
Theory of Computation
by
jothee
Veteran
(
103k
points)

3.1k
views
gate2011
theoryofcomputation
easy
nondeterminism
+13
votes
2
answers
11
GATE19981.11
Regarding the power of recognition of languages, which of the following statements is false? The nondeterministic finitestate automata are equivalent to deterministic finitestate automata. Nondeterministic Pushdown automata are equivalent to ... equivalent to deterministic Turing machines. Multitape Turing machines are available are equivalent to Singletape Turing machines.
asked
Sep 26, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

2k
views
gate1998
theoryofcomputation
easy
nondeterminism
+17
votes
2
answers
12
GATE200554
Let $N_f$ and $N_p$ denote the classes of languages accepted by nondeterministic finite automata and nondeterministic pushdown automata, respectively. Let $D_f$ and $D_p$ denote the classes of languages accepted by deterministic finite automata and deterministic pushdown automata respectively. ... $D_f = N_f \text{ and } D_p = N_p$ $D_f =N_f \text{ and } D_p \subset N_p$
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

793
views
gate2005
theoryofcomputation
easy
nondeterminism
+27
votes
7
answers
13
GATE200916, ISRO201712
Which one of the following is FALSE? There is a unique minimal DFA for every regular language Every NFA can be converted to an equivalent PDA. Complement of every contextfree language is recursive. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

4.2k
views
gate2009
theoryofcomputation
easy
isro2017
nondeterminism
+18
votes
1
answer
14
GATE199202,xx
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: In which of the cases stated below is the following statement true? "For every nondeterministic machine $M_{1}$ ... $M_{1}$ and $M_2$, the above statement true.
asked
Sep 13, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

1.1k
views
gate1992
theoryofcomputation
easy
nondeterminism
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
Standard Book Exercise Questions for Computer Science
Resource to Learn Graph Theory Interactively
Recruitment to the post of Scientist/Engineer 'SC' (Electronics, Mechanical and Computer Science)
Standard Videos for Calculus
Standard Videos for Linear Algebra
Follow @csegate
Recent questions tagged nondeterminism
Recent Blog Comments
Are the answers also present ?
@Arjun sir , Is there any page or something where...
@arjun sir but u called about providing the pdfs...
But anyhow I appreciate this. The questions of...
All these PYQ blogs and standard videos blogs...
50,376
questions
55,839
answers
192,571
comments
91,393
users