search
Log In

Recent questions tagged non-determinism

0 votes
0 answers
1
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 tree has finitely many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.)
asked Oct 13, 2019 in Theory of Computation Lakshman Patel RJIT 51 views
1 vote
1 answer
3
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, 2019 in Theory of Computation Bhaskar Singh 141 views
0 votes
0 answers
4
1 vote
1 answer
5
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
asked Mar 2, 2018 in Theory of Computation GateAspirant999 204 views
1 vote
0 answers
7
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 Shivansh Gupta 132 views
16 votes
1 answer
8
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 language generated by ... pushdown 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 Ishrat Jahan 1.9k views
12 votes
3 answers
9
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
asked Oct 4, 2014 in Theory of Computation Kathleen 1.7k views
22 votes
4 answers
10
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 single tape Turing machine and Non-deterministic single tape Turing machine Single tape Turing machine and multi-tape Turing machine
asked Sep 29, 2014 in Theory of Computation jothee 4.5k views
14 votes
2 answers
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 ... equivalent to deterministic Turing machines. Multi-tape Turing machines are available are equivalent to Single-tape Turing machines.
asked Sep 26, 2014 in Theory of Computation Kathleen 2.9k views
18 votes
2 answers
12
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 respectively. Which one ... $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 Kathleen 1.4k views
32 votes
7 answers
13
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 context-free language is recursive. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
asked Sep 22, 2014 in Theory of Computation Kathleen 5.9k views
21 votes
1 answer
14
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 non-deterministic machine $M_{1}$ there exists an equivalent deterministic machine $M_{2}$ recognizing ... $M_{1}$ is a non-deterministic Turing machine. For no machines $M_{1}$ and $M_2$, the above statement true.
asked Sep 13, 2014 in Theory of Computation Kathleen 1.8k views
To see more, click for the full list of questions or popular tags.
...