Homework Answers
Answer for 5th question is option E
reason for correctness
Decider is a machine which halts on Every input either by accepting or rejecting the input
Reason why these options are incorrect
Option a is incorrect because Turing recognizable language are superset of Turing decidable languages
Option B is incorrect because every decidable language is turing recognizable
Option C is incorrect because decider always accept or reject every input
Option d is incorrect because recognizer M always halt on the input string which is in the language of M but it may or may not halt on.the input which are not in the language of M . Recognizer is turing machine which accept turing recognizable language
Add Answer to:
5. (1 point) Which of the following statements is true? A. Recognizable languages are a subset...
Q1: Which of the following claims are true?* 1 point The recognizable languages are closed under union and intersection...
Q1: Which of the following claims are true?* 1 point The recognizable languages are closed under union and intersection The decidable lanquages are closed under union and intersection The class of undecidable languages contains the class of recognizable anguages 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 that apply) 1 point EDFA-{ «A> 1 A is a DFA and...
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...
19. (1 point) Suppose that L is undecidable and L is recognizable. Which of the following...
19. (1 point) Suppose that L is undecidable and L is recognizable. Which of the following could be false? A. I is co-Turing recognizable. B. I is not recognizable. C. I is undecidable. D. L* is not recognizable. E. None of the above. 20. (2 points) Let ETM {(M)|L(M) = 0} and EQTM = {(M1, M2)|L(Mi) = L(M2)}. We want to show that EQTM is undecidable by reducing Etm to EQTM and we do this by assuming R is a...
Question 5 10 pts Select all the statements below which are true: The grammar below is...
Question 5 10 pts Select all the statements below which are true: The grammar below is CS. SaSa bb O Any CS language is RE. The language L = {a”b"c" : n > 1}is CF. The language L = {wwR : w€ {a, b}" } is DCF, CF, CS, REC, and RE. There are languages which are not accepted by TMs. Any REC language is accepted by some Decider (a TM that halts for every input).
11. (1 point) Which of the following sets are countable? A. {0,1}" B. {LL C{0,1}} C....
11. (1 point) Which of the following sets are countable? A. {0,1}" B. {LL C{0,1}} C. The set of all numbers {al a € Z or a = be where b, c € Z}, where Z is the set of all integers. D. Both A and C. E. All of A,B and C. 12. (1 point) How do we know that some languages may not be Turing-recognizable? A. Atm is an example of a language which is not Turing-recognizable. B....
13. (1 point) Which of the following statement could be false where Lį and L2 are...
13. (1 point) Which of the following statement could be false where Lį and L2 are decidable lan- guages? A. Li · L2 is decidable. B. Li Lis undecidable. C. Lin L2 is decidable. D. LI U L2 is decidable. E. None of the above. 14. (1 point) Which of the following statement could be false where Lj is decidable and L2 is recognizable? A. Li · L2 is recognizable. B. Li · L2 is decidable. C. Lin L2 is...
7. (1 point) The collection of recognizable languages is closed under: A. union. B. concatenation. C....
7. (1 point) The collection of recognizable languages is closed under: A. union. B. concatenation. C. star. D. intersection. E. All of the above. Page 3 of 8 8. (1 point) L is decided by a deterministic) TM containing 100 tapes in time t(n) where n denotes the length of an input string. Which one of the following represents the time complexity of an equivalent single tape (deterministic) TM which decides L? A. Oft(n) 100). B. Oſt(n)). C. O(t(n)99). D....
1. (1 point) Which of the following is true? A. Every regular language is a context-free...
1. (1 point) Which of the following is true? A. Every regular language is a context-free language. B. Every context-free language is a regular language. C. If a language is context-free, then there exists a pushdown automata to recognize it. D. The set of context free languages is strictly larger than the set of regular languages. E. Each of A,C, and D is true. 2. (1 point) The following diagram shows a context free grammar with start variable S and...
1. (1 point) Which of the following is true? A. Every regular language is a context-free...
1. (1 point) Which of the following is true? A. Every regular language is a context-free language. B. Every context-free language is a regular language. C. If a language is context-free, then there exists a pushdown automata to recognize it. D. The set of context free languages is strictly larger than the set of regular languages. E. Each of A,C, and D is true. 2. (1 point) The following diagram shows a context free grammar with start variable S and...
If L1 and L2 are Regular Languages, then L1 ∪ L2 is a CFL. Group of answer choices...
If L1 and L2 are Regular Languages, then L1 ∪ L2 is a CFL. Group of answer choices True False Flag this Question Question 61 pts If L1 and L2 are CFLs, then L1 ∩ L2 and L1 ∪ L2 are CFLs. Group of answer choices True False Flag this Question Question 71 pts The regular expression ((ac*)a*)* = ((aa*)c*)*. Group of answer choices True False Flag this Question Question 81 pts Some context free languages are regular. Group of answer choices True...
Q1: Which of the following claims are true?* 1 point The recognizable languages are closed under union and intersection The decidable lanquages are closed under union and intersection The class of undecidable languages contains the class of recognizable anguages 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 that apply) 1 point EDFA-{ «A> 1 A is a DFA and...
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...
19. (1 point) Suppose that L is undecidable and L is recognizable. Which of the following could be false? A. I is co-Turing recognizable. B. I is not recognizable. C. I is undecidable. D. L* is not recognizable. E. None of the above. 20. (2 points) Let ETM {(M)|L(M) = 0} and EQTM = {(M1, M2)|L(Mi) = L(M2)}. We want to show that EQTM is undecidable by reducing Etm to EQTM and we do this by assuming R is a...
Question 5 10 pts Select all the statements below which are true: The grammar below is CS. SaSa bb O Any CS language is RE. The language L = {a”b"c" : n > 1}is CF. The language L = {wwR : w€ {a, b}" } is DCF, CF, CS, REC, and RE. There are languages which are not accepted by TMs. Any REC language is accepted by some Decider (a TM that halts for every input).
11. (1 point) Which of the following sets are countable? A. {0,1}" B. {LL C{0,1}} C. The set of all numbers {al a € Z or a = be where b, c € Z}, where Z is the set of all integers. D. Both A and C. E. All of A,B and C. 12. (1 point) How do we know that some languages may not be Turing-recognizable? A. Atm is an example of a language which is not Turing-recognizable. B....
13. (1 point) Which of the following statement could be false where Lį and L2 are decidable lan- guages? A. Li · L2 is decidable. B. Li Lis undecidable. C. Lin L2 is decidable. D. LI U L2 is decidable. E. None of the above. 14. (1 point) Which of the following statement could be false where Lj is decidable and L2 is recognizable? A. Li · L2 is recognizable. B. Li · L2 is decidable. C. Lin L2 is...
7. (1 point) The collection of recognizable languages is closed under: A. union. B. concatenation. C. star. D. intersection. E. All of the above. Page 3 of 8 8. (1 point) L is decided by a deterministic) TM containing 100 tapes in time t(n) where n denotes the length of an input string. Which one of the following represents the time complexity of an equivalent single tape (deterministic) TM which decides L? A. Oft(n) 100). B. Oſt(n)). C. O(t(n)99). D....
1. (1 point) Which of the following is true? A. Every regular language is a context-free language. B. Every context-free language is a regular language. C. If a language is context-free, then there exists a pushdown automata to recognize it. D. The set of context free languages is strictly larger than the set of regular languages. E. Each of A,C, and D is true. 2. (1 point) The following diagram shows a context free grammar with start variable S and...
1. (1 point) Which of the following is true? A. Every regular language is a context-free language. B. Every context-free language is a regular language. C. If a language is context-free, then there exists a pushdown automata to recognize it. D. The set of context free languages is strictly larger than the set of regular languages. E. Each of A,C, and D is true. 2. (1 point) The following diagram shows a context free grammar with start variable S and...
Most questions answered within 3 hours.
-
How can I solve the following using a TI83
Claim: Most adults would erase all of...
asked 4 minutes ago -
Analysis of 3-ethyl-3-buten-2-ol gave C, 72.13%; H, 11.92%.
Calculate the percent deviation of these results from...
asked 1 minute ago -
Which VALS segment is most likely to have a top of the line
brand new (2015)...
asked 5 minutes ago -
Write a program to score the paper-rock-scissor game. Each of
two users types in either P,R...
asked 25 minutes ago -
Calculate the equillibrium constent K for a redox reaction that
has E°cell = -.98 V at...
asked 37 minutes ago -
A concave spherical mirror has a radius of curvature of
magnitude 19.6 cm.
(a) Find the...
asked 39 minutes ago -
3. draw a diagram of the magnetic field:
a. around a long straight wire with a...
asked 38 minutes ago -
If you titrated 30.0 mL of 0.1 M HCl with 0.1 M NaOH, indicate
the approximate...
asked 46 minutes ago -
NADH passes electrons into the electron transport chain. List
the carriers that would receive the electrons,...
asked 54 minutes ago -
A cylindrical cable with a resistivity of 1.6x10-8 Ω·m and cross
sectional area of 3x10-5 m^2...
asked 54 minutes ago -
True or False.
A consumer with convex preferences who is indifferent between
the bundles (5,2) and...
asked 58 minutes ago -
A diamond's index of refraction for red light, 656 nm, is 2.410,
while that for blue...
asked 1 hour ago