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 questions tagged nondeterminism
0
votes
0
answers
1
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)

37
views
theoryofcomputation
finiteautomata
nondeterminism
nfa
finiteautomata
+1
vote
1
answer
2
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)

57
views
theoryofcomputation
finiteautomata
nfa
nondeterminism
0
votes
0
answers
3
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
(
1.5k
points)

42
views
minimalstateautomata
theoryofcomputation
finiteautomata
nondeterminism
+1
vote
1
answer
4
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.8k
points)

92
views
finiteautomata
nondeterminism
theoryofcomputation
+1
vote
0
answers
5
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
(
205
points)

66
views
theoryofcomputation
nondeterminism
madeeasytestseries
madeeasytestseries2018
+1
vote
0
answers
6
#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)

89
views
automate
turingmachine
pushdownautomata
nondeterminism
+3
votes
1
answer
7
Peter Linz Edition 4 Exercise 7.1 Question 4.h,4.j (Page No. 183)
Construct npda for the following languages on ∑ = {a,b,c} 1) L = { w : na(w) = 2*nb(w) } 2) L = { w : 2*na(w) <= nb(w) <= 3*na(w) }
asked
Apr 30, 2017
in
Theory of Computation
by
Vishal Goel
Active
(
1.7k
points)

333
views
pushdownautomata
theoryofcomputation
npda
nondeterminism
peterlinz
contextfreelanguages
+13
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
(
19.1k
points)

1.1k
views
gate2004it
theoryofcomputation
easy
nondeterminism
+9
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
(
59.9k
points)

797
views
gate1994
theoryofcomputation
easy
nondeterminism
+19
votes
3
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
(
115k
points)

2.8k
views
gate2011
theoryofcomputation
easy
nondeterminism
+12
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
(
59.9k
points)

1.8k
views
gate1998
theoryofcomputation
easy
nondeterminism
+15
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
(
59.9k
points)

676
views
gate2005
theoryofcomputation
easy
nondeterminism
+24
votes
5
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
(
59.9k
points)

3.9k
views
gate2009
theoryofcomputation
easy
isro2017
nondeterminism
+16
votes
1
answer
14
GATE199202,xx
02. 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}$ there exists an equivalent deterministic machine ... $M_{1}$ and $M_2$, the above statement true.
asked
Sep 13, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.9k
points)

901
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
IIT Gandhinagar review
AIR175 : GO is enough
GATE 2019 My reasoned routine. (AIR 558)
if i can you also can
M.S admissions help
Follow @csegate
Recent questions tagged nondeterminism
Recent Blog Comments
can anybody compare it with other new iits such...
can i get a call on 580 (OBCNCL)
Many times Anger , Aggression and Fear push...
One word would be "Priorities" Second word shall...
What's interesting to me is that despite having...
48,691
questions
52,776
answers
183,434
comments
68,389
users