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
Recent questions tagged nondeterminism
0
votes
0
answers
1
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
in
Theory of Computation
by
sripo
Junior
(
509
points)

32
views
minimalstateautomata
theoryofcomputation
finiteautomata
nondeterminism
+1
vote
1
answer
2
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
in
Theory of Computation
by
GateAspirant999
Active
(
2.7k
points)

64
views
finiteautomata
nondeterminism
theoryofcomputation
+1
vote
0
answers
3
#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.5k
points)

80
views
automate
turingmachine
pushdownautomata
nondeterminism
+2
votes
0
answers
4
How to construct npda for given languages (Peter Linz 3rd Ed, Exercise 7, Ques 4)?
asked
Apr 30, 2017
in
Theory of Computation
by
Vishal Goel
Active
(
1.5k
points)

252
views
pushdownautomata
theoryofcomputation
npda
nondeterminism
peterlinz
contextfreelanguages
+13
votes
1
answer
5
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)

971
views
gate2004it
theoryofcomputation
easy
nondeterminism
+9
votes
3
answers
6
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.6k
points)

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

2.4k
views
gate2011
theoryofcomputation
easy
nondeterminism
+12
votes
2
answers
8
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.6k
points)

1.6k
views
gate1998
theoryofcomputation
easy
nondeterminism
+15
votes
2
answers
9
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. ... = N_p$ $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.6k
points)

546
views
gate2005
theoryofcomputation
easy
nondeterminism
+24
votes
5
answers
10
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.6k
points)

3.5k
views
gate2009
theoryofcomputation
easy
isro2017
nondeterminism
+15
votes
1
answer
11
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 ... . $M_{1}$ is a nondeteministic Turing machine. For no machines $M_{1}$ and $M_2$, the above statement true.
asked
Sep 13, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.6k
points)

742
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 Madras Phd
Databases GO Classroom
I need help in Preparation for 2020
Happy Birthday Sir Arjun
NIELIT EXAM DATE 2018
Follow @csegate
Gatecse
Recent questions tagged nondeterminism
Recent Blog Comments
They are not reviewed by GO. But they will be...
What is the job profile for candidate at AAI and...
GATEBOOK2019 DS1 doesn't have solutions,...
How to prepare for aptitude part?
Belated happy birthday to you, sir :)
42,294
questions
48,415
answers
153,516
comments
62,660
users