Dark Mode

Recent questions tagged non-determinism

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.)

admin asked in Theory of Computation Oct 12, 2019

by admin

465 views

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?

Bhaskar Singh asked in Theory of Computation Mar 3, 2019

by Bhaskar Singh

580 views

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?

Bhaskar Singh asked in Theory of Computation Feb 20, 2019

by Bhaskar Singh

686 views

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?

sripo asked in Theory of Computation Oct 16, 2018

by sripo

406 views

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^n|n=2k,kϵN\}$ and 2 $\{a^{2n}|n=2k,kϵN\}$ and 2 $\{a^n|n=2k,kϵ N\}$ and 3 $\{a^{2n}|n=2k,kϵ N\}$ and 3

GateAspirant999 asked in Theory of Computation Mar 2, 2018

by GateAspirant999

1.1k views

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

Sukhdip Singh asked in Theory of Computation Jan 17, 2018

by Sukhdip Singh

354 views

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 ?

Shivansh Gupta asked in Theory of Computation Jul 6, 2017

by Shivansh Gupta

346 views

26 votes

1 answer

8

GATE IT 2004 | Question: 9
Which one of the following statements is FALSE? There exist context-free languages such that all the context-free grammars generating them are ambiguous An unambiguous context-free grammar always has a unique parse tree for each string of the ... automata always accept the same set of languages A finite set of string from some alphabet is always a regular language

Ishrat Jahan asked in Theory of Computation Nov 1, 2014

by Ishrat Jahan

6.4k views

19 votes

3 answers

9

GATE CSE 1994 | Question: 1.16
Which of the following conversions is not possible (algorithmically)? Regular grammar to context free grammar Non-deterministic FSA to deterministic FSA Non-deterministic PDA to deterministic PDA Non-deterministic Turing machine to deterministic Turing machine

Kathleen asked in Theory of Computation Oct 4, 2014

7.5k views

29 votes

3 answers

10

GATE CSE 2011 | Question: 8
Which of the following pairs have DIFFERENT expressive power? Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA) Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA) Deterministic ... Turing machine and Non-deterministic single tape Turing machine Single tape Turing machine and multi-tape Turing machine

go_editor asked in Theory of Computation Sep 29, 2014

9.4k views

20 votes

1 answer

11

GATE CSE 1998 | Question: 1.11
Regarding the power of recognition of languages, which of the following statements is false? The non-deterministic finite-state automata are equivalent to deterministic finite-state automata. Non-deterministic Push-down automata are equivalent ... to deterministic Turing machines. Multi-tape Turing machines are available are equivalent to Single-tape Turing machines.

Kathleen asked in Theory of Computation Sep 25, 2014

8.2k views

27 votes

2 answers

12

GATE CSE 2005 | Question: 54
Let $N_f$ and $N_p$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $D_f$ and $D_p$ denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata ... $D_f = N_f \text{ and } D_p = N_p$ $D_f =N_f \text{ and } D_p \subset N_p$

Kathleen asked in Theory of Computation Sep 22, 2014

4.2k views

28 votes

1 answer

13

GATE CSE 1992 | Question: 02,xx
In which of the cases stated below is the following statement true? "For every non-deterministic machine $M_{1}$ there exists an equivalent deterministic machine $M_{2}$ recognizing the same language". $M_{1}$ ... $M_{1}$ and $M_2$, the above statement true.

Kathleen asked in Theory of Computation Sep 13, 2014

7.4k views

To see more, click for the full list of questions or popular tags.

Recent questions tagged non-determinism