Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
10 Cards in this Set
- Front
- Back
|
True or False: There is a language that is decidable and its complement is not decidable |
False: Closure under complement |
|
|
True or False: There is a language that is recognizable and its complement is not recognizable |
True: ATM is an example |
|
|
True or False: Rice’s theorem states that many languages are not recognizable. |
False: Should say“not decidable.” |
|
|
True or False: The problem of determining whether a TM accepts at least 7 strings isundecidable |
True: Rice’s theorem. |
|
|
True or False: The problem of determining whether a TM has at least 7 states is undecidable |
False |
|
|
Multiple Choice: The problem of deciding whether a given TM accepts some string of length5 is: (a) Undecidable because if a decider existed, then one can decide whether or not a DFAhas empty language. (b) Undecidable because of Rice’s Theorem. (c) Decidable because we can just test all strings of length 5 simultaneously and see if anyaccept. (d) Decidable because we can decide it using a decider for the acceptance problem forLBAs. (e) None of the above is true |
(b) Undecidable because of Rice’s Theorem. |
|
|
Multiple Choice: The acceptance problem for LBAs is: (a) Decidable because we can detect an infinite loop in a finite amount of time. (b) Decidable because there cannot actually be an infinite loop in an LBA. (c) Undecidable because this is just the acceptance problem for TMs but for a restrictedclass of them (so the answer of decidability does not change). (d) Undecidable because we can reduce from the emptiness problem for LBAs which isundecidable. (e) None of the above is true |
(a) Decidable because we can detect an infinite loop in a finite amount of time. |
|
|
Multiple Choice: For a given TM and input, consider the language of accepting computationhistories of that TM on that input. Then this language is: (a) Decidable because in all cases this language is finite. (b) Decidable because we can simulate the TM until it halts. (c) Undecidable because if we can find out if this language is empty or not, we can solvethe acceptance problem for TMs. (d) Undecidable because determining computation histories is undecidable, so acceptingcomputation histories is also undecidable. (e) None of the above is true |
(a) Decidable because in all cases this language is finite. |
|
|
Multiple Choice: The statement A_NFA ≤ A_DFA means: (a) A_NFA reduces to A_DFA. (b) A_DFA reduces to A_NF A. (c) If A_NFA is decidable, then A_DFA is decidable.(d) If A_DFA is undecidable, then A_NFA is undecidable. (e) None of the above is true. |
(a) A_NFA reduces to A_DFA. |
|
|
My friend wants to apply Rice’s theorem to the language {<M> : Maccepts \ep and has at least 5 states}. I note that he cannot apply Rice’s theorem for thislanguage. What is the reason why he cannot? |
Because this language is not a property of the language of TMs |
