Homework Answers
In case of any doubts, please revert back.
Theorems used:-
L1 is undecidable and L1 ≤m L2, then L2 is undecidable.
L2 is recognizable and L1 ≤m L2 , then L1 is recognizable.
Add Answer to:
(6 pts- 2 pts each) Let L be a language such that L Sm A your answers to the following questions: and AM Sm L. Just...
(6 pts-2 pts each) Let L be a language such that L Sm Any and Ay Sm L. Justify your answers to the following questi...
(6 pts-2 pts each) Let L be a language such that L Sm Any and Ay Sm L. Justify your answers to the following questions: 3. TM a) Is L decidable? b) Is L Turing-recognizable? c) Is L Turing-recognizable?
(6 pts-2 pts each) Let L be a language such that L Sm Any and Ay Sm L. Justify your answers to the following questions: 3. TM a) Is L decidable? b) Is L Turing-recognizable? c) Is L Turing-recognizable?
Classify the language { (G) | G is a CFG, L(G) contains a palindrome}\ as (a) decidable (b) Turing-recognizable but not...
Classify the language { (G) | G is a CFG, L(G) contains a palindrome}\ as (a) decidable (b) Turing-recognizable but not co-Turing recognizable (c) co-Turing recognizable but not Turing-recognizable (d) neither Turing nor co-Turing recognizable Justify your answer
Please also note that there might be multiple answers for each question. Q1: Which of the following claims are true?*...
Please also note that there might be multiple answers for each
question.
Q1: Which of the following claims are true?* 1 point The recognizable languages are closed under union and intersection The decidable languages are closed under union and intersection The class of undecidable languages contains the class of recognizable languages For every language A, at least one of A or A*c is recognizable Other: This is a required question Q2: Which of the following languages are recognizable? (Select all...
Let Azfa"b"c" I n 0 }. Answer each of the following question: 1. 2. 3. 4....
Let Azfa"b"c" I n 0 }. Answer each of the following question: 1. 2. 3. 4. Is A a regular language? Is A a context free language? Is A Turing recognizable? Is A Turing decidable?
1. Let n be a positive integer. Classify the languages (i) R = {(M)IM is a...
1. Let n be a positive integer. Classify the languages (i) R = {(M)IM is a TM and L(M) contains exactly n strings) (ii) S- (M)|M is a TM and L(M) contains more than n strings as (a) decidable, (b) Turing-recognizable but not co-Turing-recognizable, (c) co-Turing-recognizable but not Turing-recognizable, (d) neither Turing-recognizable nor co-Turing-recognizable. Justify your answers.
Give examples of the following sets (languages): a. A set (language) that is Turing-recognizable but not...
Give examples of the following sets (languages): a. A set (language) that is Turing-recognizable but not decidable b. A set (language) that is decidable but not context-free c. A set (language) that is context-free but not regular
Let n be a positive integer. Classify the languages R = { (M) | M is a TM and L(M) contains exactly n strings} S = { (M)...
Let n be a positive integer. Classify the languages R = { (M) | M is a TM and L(M) contains exactly n strings} S = { (M) | M is a TM and L(M) contains more than n strings} as (a) decidable (b) Turing-recognizable but not co-Turing recognizable (c) co-Turing recognizable but not Turing-recognizable (d) neither Turing nor co-Turing recognizable
Only 5-9 please 1. (10 points) True/False. Briefly justify your answer for each statement. 1) Any subset of a decidable...
Only 5-9 please
1. (10 points) True/False. Briefly justify your answer for each statement. 1) Any subset of a decidable set is decidable 2) Any subset of a regular language is decidable 3) Any regular language is decidable 4) Any decidable set is context-free 5) There is a recognizable but not decidable language 6) Recognizable sets are closed under complement. 7) Decidable sets are closed under complement. 8) Recognizable sets are closed under union 9) Decidable sets are closed under...
I need 7 - 10. Ignore others please! 1. (10 points) True/False. Briefly justify your answer for each statement. 1) Any...
I need 7 - 10. Ignore others please!
1. (10 points) True/False. Briefly justify your answer for each statement. 1) Any subset of a decidable set is decidable 2) Any subset of a regular language is decidable 3) Any regular language is decidable 4) Any decidable set is context-free 5) There is a recognizable but not decidable language 6) Recognizable sets are closed under complement. 7) Decidable sets are closed under complement. 8) Recognizable sets are closed under union 9)...
2. Let L = {hMi: M is a Turing machine that accepts at least two binary strings}. a) Define the notions of a recognisabl...
2. Let L = {hMi: M is a Turing machine that accepts at least two
binary strings}. a) Define the notions of a recognisable language
and an undecidable language. [5 marks] b) Is L Turing-recognisable?
Justify your answer with an informal argument. [5 marks] c) Prove
that L is undecidable. (Hint: use Rice’s theorem.) [20 marks] d)
Bonus: Justify with a formal proof your answer to b). [20
marks]
2. Let L-M M): M is a Turing machine that accepts...
(6 pts-2 pts each) Let L be a language such that L Sm Any and Ay Sm L. Justify your answers to the following questions: 3. TM a) Is L decidable? b) Is L Turing-recognizable? c) Is L Turing-recognizable?
(6 pts-2 pts each) Let L be a language such that L Sm Any and Ay Sm L. Justify your answers to the following questions: 3. TM a) Is L decidable? b) Is L Turing-recognizable? c) Is L Turing-recognizable?
Please also note that there might be multiple answers for each
question.
Q1: Which of the following claims are true?* 1 point The recognizable languages are closed under union and intersection The decidable languages are closed under union and intersection The class of undecidable languages contains the class of recognizable languages For every language A, at least one of A or A*c is recognizable Other: This is a required question Q2: Which of the following languages are recognizable? (Select all...
Let Azfa"b"c" I n 0 }. Answer each of the following question: 1. 2. 3. 4. Is A a regular language? Is A a context free language? Is A Turing recognizable? Is A Turing decidable?
1. Let n be a positive integer. Classify the languages (i) R = {(M)IM is a TM and L(M) contains exactly n strings) (ii) S- (M)|M is a TM and L(M) contains more than n strings as (a) decidable, (b) Turing-recognizable but not co-Turing-recognizable, (c) co-Turing-recognizable but not Turing-recognizable, (d) neither Turing-recognizable nor co-Turing-recognizable. Justify your answers.
Only 5-9 please
1. (10 points) True/False. Briefly justify your answer for each statement. 1) Any subset of a decidable set is decidable 2) Any subset of a regular language is decidable 3) Any regular language is decidable 4) Any decidable set is context-free 5) There is a recognizable but not decidable language 6) Recognizable sets are closed under complement. 7) Decidable sets are closed under complement. 8) Recognizable sets are closed under union 9) Decidable sets are closed under...
I need 7 - 10. Ignore others please!
1. (10 points) True/False. Briefly justify your answer for each statement. 1) Any subset of a decidable set is decidable 2) Any subset of a regular language is decidable 3) Any regular language is decidable 4) Any decidable set is context-free 5) There is a recognizable but not decidable language 6) Recognizable sets are closed under complement. 7) Decidable sets are closed under complement. 8) Recognizable sets are closed under union 9)...
2. Let L = {hMi: M is a Turing machine that accepts at least two
binary strings}. a) Define the notions of a recognisable language
and an undecidable language. [5 marks] b) Is L Turing-recognisable?
Justify your answer with an informal argument. [5 marks] c) Prove
that L is undecidable. (Hint: use Rice’s theorem.) [20 marks] d)
Bonus: Justify with a formal proof your answer to b). [20
marks]
2. Let L-M M): M is a Turing machine that accepts...
Most questions answered within 3 hours.
-
A small body of mass m performs small oscillations sliding (no
rolling) along the bottom of...
asked 1 minute ago -
The electric field in the region between two oppositely charged,
parallel, conducting plates has a magnitude...
asked 1 minute ago -
A simple random sample was taken to test the claim that the
population mean is no...
asked 1 hour ago -
A set of length measurements are obtained with the values 165.6
± 0.3, 165.1± 0.4,166.4± 1.0,...
asked 1 hour ago -
1. Which of the following is true about unconscionable
contracts?
a. A term is substantially unconscionable...
asked 15 minutes ago -
A company is interested in estimating the costs of lunch
in their cafeteria. After surveying employees,...
asked 47 minutes ago -
A 0.2m diameter ball with an initial velocity of 8m/s rolls up a
hill without slipping....
asked 30 minutes ago -
I want to redraft the solution, using other words , use your own
words don't copy...
asked 19 minutes ago -
Hyundai Motors is considering threesites—A, B,C —at which to
locate a factory to build its new-model...
asked 21 minutes ago -
Learning Outcomes:
Upon the successful completion of this module, you should
understand the following concepts:
Strategic...
asked 22 minutes ago -
Identify four of the five major types of organizations within
the federal bureaucracy, and give examples...
asked 30 minutes ago -
The following data have been obtained
for the effect of solvent composition on the solubility of...
asked 31 minutes ago