CISC 4090/5200 Quiz 3 Solutions
Note: TM = Turing Machine PDA = Push Down Automata
True/False (6 points each)
1. A PDA recognize 0n1n? T F
Copyright By PowCoder代写 加微信 powcoder
2. A deterministic and a nondeterministic PDA recognize the same set of languages. T F
3. A PDA can sometimes recognize languages that a TM cannot since a PDA has T F a stack and a Turing Machine does not.
4. Both a Turing Machine and PDA have infinite amounts of storage. T F
5. A language can be Turing decidable but not Turing recognizable T F
6. ACFG is decidable T F
7. The Halting problem is decidable T F
8. There is a one-to-one correspondence between the natural and real numbers T F
9. We will always be able to tell if a TM accepts or rejects a string
10. The number of English sentences is countable.
Short Answer: Each question can be answered with a single sentence.
1. A Language L is Turing Recognizable if
a TM accepts all strings in L
2. A Language L is Turing Decidable if
a TM accepts all strings in L and rejects all strings not in L
(10 points each)
3. What does the language ADFA represent? I suggest you answer this by describing what elements are in the language.
All 2-tuples where the first element is a valid DFA and the second element is a string accepted by the DFA.
4. Describe the halting problem (i.e., what it is):
Determine whether a program halts on the input or does not halt (infinite loops).
Name: ___________________________________
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com