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
Homework Answers
a) ATM={<T,w>|M is a TM wbelongs to L(M)}. is language which is not decidable but can be accepted by TM
b) L={0n1n2n|n>=0} this should have 2 memories and PDA will have 1 stack memory, so this language cannot be accepted by PDA ==> this is not CFL
c) L={0n1nn>=0} Here 1 memory element should have and regular languages accepted m/c will not havememoriy, so this is not regular
Add Answer to:
Give examples of the following sets (languages):
a. A set (language) that is Turing-recognizable but not...
determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give...
determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give a DFA that accepts the language, a regular expression that generates the language, and a maximal list of strings that are pairwise distinguishable with respect to the language. For languages that are context-free but not regular, prove that the language is not regular and either give a context- free grammar that generates the language or a pushdown automaton that accepts the language. You need...
determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give...
determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give a DFA that accepts the language, a regular expression that generates the language, and a maximal list of strings that arc pairwise distinguishable with respect to the language. For languages that are context-free but not regular, prove that the language is not regular and either give a context- free grammar that generates the language or a pushdown automaton that accepts the language. You need...
2. Properties of the following: (a) Regular languages (b) Context-free languages (c) Regular expressions (d) Non-deterministic...
2. Properties of the following: (a) Regular languages (b) Context-free languages (c) Regular expressions (d) Non-deterministic finite automaton (e) Turing-recognizable and Turing-decidable languages (f) A <m B and what we can then determine (g) A <p B and what we can then determine (h) NP-hard and NP-complete.
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...
5. (1 point) Which of the following statements is true? A. Recognizable languages are a subset...
5. (1 point) Which of the following statements is true? A. Recognizable languages are a subset of the decidable languages. B. Some decidable languages may not be recognizable. C. A decider for a language must accept every input. D. A recognizer for a language doesn't halt. E. A decider halts on every input by either going to an accept state or a reject state. 6. (1 point) Which of the following could be false for the language L = {abclixj...
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
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)...
Quick Quiz Is the following true? 1. If L is Turing-decidable, L is Turing- recognizable If...
Quick Quiz Is the following true? 1. If L is Turing-decidable, L is Turing- recognizable If L is Turing-recognizable, L is Turing- decidable 2. 3. If L is Turing-decidable, so is t 4. If L is Turing-recognizable, so is L 5. If both L and L are Turing-recognizable, L is Turing-decidable
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?
determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give a DFA that accepts the language, a regular expression that generates the language, and a maximal list of strings that are pairwise distinguishable with respect to the language. For languages that are context-free but not regular, prove that the language is not regular and either give a context- free grammar that generates the language or a pushdown automaton that accepts the language. You need...
determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give a DFA that accepts the language, a regular expression that generates the language, and a maximal list of strings that arc pairwise distinguishable with respect to the language. For languages that are context-free but not regular, prove that the language is not regular and either give a context- free grammar that generates the language or a pushdown automaton that accepts the language. You need...
2. Properties of the following: (a) Regular languages (b) Context-free languages (c) Regular expressions (d) Non-deterministic finite automaton (e) Turing-recognizable and Turing-decidable languages (f) A <m B and what we can then determine (g) A <p B and what we can then determine (h) NP-hard and NP-complete.
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...
5. (1 point) Which of the following statements is true? A. Recognizable languages are a subset of the decidable languages. B. Some decidable languages may not be recognizable. C. A decider for a language must accept every input. D. A recognizer for a language doesn't halt. E. A decider halts on every input by either going to an accept state or a reject state. 6. (1 point) Which of the following could be false for the language L = {abclixj...
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)...
Quick Quiz Is the following true? 1. If L is Turing-decidable, L is Turing- recognizable If L is Turing-recognizable, L is Turing- decidable 2. 3. If L is Turing-decidable, so is t 4. If L is Turing-recognizable, so is L 5. If both L and L are Turing-recognizable, L is Turing-decidable
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?
Most questions answered within 3 hours.
-
Given input { 66, 28, 43, 29, 44, 69, 19 } and a hash function
h(x)...
asked 11 minutes ago -
A pebble with mass m is thrown straight up with an initial speed
v0 so that...
asked 15 minutes ago -
Let X be a discrete random variable that follows a
binomial distribution with n = 11...
asked 24 minutes ago -
The equilibrium constant, K, for the following reaction is
1.29×10-2 at 600
K.
COCl2(g) --->
CO(g)...
asked 37 minutes ago -
It is known that 72% of people have a favorable opinion of their
local police force....
asked 40 minutes ago -
A vertical straight wire carrying an upward 26-A current exerts
an attractive force per unit length...
asked 53 minutes ago -
For the purposes of this assignment, you are to choose an
adaptive trait common to more...
asked 1 hour ago -
Two identical flutes can play middle C (262 Hz) at 20◦C. How
many beats per second...
asked 1 hour ago -
Potassium phosphate and calcium chloride react in a double
replacement reaction. To produce 1.0 moles of...
asked 1 hour ago -
Sparky, Co. purchased land as a factory site for $600,000.
Sparky paid $42,000 to tear down...
asked 1 hour ago -
A Chi-square distribution with 14 degrees of freedom is a
correct model for
Question 8 options:...
asked 1 hour ago -
In a group of 45 mice, there are 10 that have a certain genetic
character. suppose...
asked 1 hour ago