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
Homework Answers
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}
Turing-recognizability means that there is a program that can confirm that a string w is in a language, and co-Turing-recognizability means that there is a program that can confirm that a string w is not in the language.
Therefore given language is co-Turing recognizable but not Turing-recognizable.
Add Answer to:
Let n be a positive integer. Classify the languages R = { (M) | M is a TM and L(M) contains exactly n strings} S = { (M)...
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.
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...
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...
Help me answer this question plz! 4. Let L = { (A) M is a Turing...
Help me answer this question plz!
4. Let L = { (A) M is a Turing machine that accepts more than one string } a) Define the notions of Turing-recognisable language and undecidable language. b) Is L Turing-recognisable? Justify your answer with an informal argument. c) Justify with a formal proof your answer to b) d) Prove that L is undecidable. (Hint: use Rice's theorem.) e) Modify your answer to b) when instead of L you have the language Ln...
3. These languages are not regular. For each, list three strings that would work in a...
3. These languages are not regular. For each, list three strings that would work in a Pumping Lemma proof. Then, use one of them to show the language is not regular. But not a. a. L = {ww | w Î {a, b}*} b. L = {anba2n | n >= 0} c. {w Î S* | w contains more a’s than b’s}.
1. Let m be a nonnegative integer, and n a positive integer. Using the division algorithm...
1. Let m be a nonnegative integer, and n a positive integer. Using the division algorithm we can write m=qn+r, with 0 <r<n-1. As in class define (m,n) = {mc+ny: I,Y E Z} and S(..r) = {nu+ru: UV E Z}. Prove that (m,n) = S(n,r). (Remark: If we add to the definition of ged that gedan, 0) = god(0, n) = n, then this proves that ged(m, n) = ged(n,r). This result leads to a fast algorithm for computing ged(m,...
I got a C++ problem. Let n be a positive integer and let S(n) denote the...
I got a C++ problem.
Let n be a positive integer and let S(n) denote the number of divisors of n. For example, S(1)- 1, S(4)-3, S(6)-4 A positive integer p is called antiprime if S(n)くS(p) for all positive n 〈P. In other words, an antiprime is a number that has a larger number of divisors than any number smaller than itself. Given a positive integer b, your program should output the largest antiprime that is less than or equal...
2. Let n be a positive integer. Denote the number of positive integers less than n and rela- tive...
number thoery
just need 2 answered
2. Let n be a positive integer. Denote the number of positive integers less than n and rela- tively prime to n by p(n). Let a, b be positive integers such that ged(a,n) god(b,n)-1 Consider the set s, = {(a), (ba), (ba), ) (see Prollern 1). Let s-A]. Show that slp(n). 1. Let a, b, c, and n be positive integers such that gcd(a, n) = gcd(b, n) = gcd(c, n) = 1 If...
2. Let L-M M): M is a Turing machine that accepts at least two binary strings. a) Define the notions of a recognisable...
2. Let L-M M): 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 [5 marks] b) Is L Turing-recognisable? Justify your answer with an informal argument. c) Prove that L is undecidable. (Hint: use Rice's theorem.) [20 marks] 20 marks] d) Bonus: Justify with a formal proof your answer to b).
2. Let L-M M): M is a Turing machine that accepts at...
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.
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...
Help me answer this question plz!
4. Let L = { (A) M is a Turing machine that accepts more than one string } a) Define the notions of Turing-recognisable language and undecidable language. b) Is L Turing-recognisable? Justify your answer with an informal argument. c) Justify with a formal proof your answer to b) d) Prove that L is undecidable. (Hint: use Rice's theorem.) e) Modify your answer to b) when instead of L you have the language Ln...
1. Let m be a nonnegative integer, and n a positive integer. Using the division algorithm we can write m=qn+r, with 0 <r<n-1. As in class define (m,n) = {mc+ny: I,Y E Z} and S(..r) = {nu+ru: UV E Z}. Prove that (m,n) = S(n,r). (Remark: If we add to the definition of ged that gedan, 0) = god(0, n) = n, then this proves that ged(m, n) = ged(n,r). This result leads to a fast algorithm for computing ged(m,...
I got a C++ problem.
Let n be a positive integer and let S(n) denote the number of divisors of n. For example, S(1)- 1, S(4)-3, S(6)-4 A positive integer p is called antiprime if S(n)くS(p) for all positive n 〈P. In other words, an antiprime is a number that has a larger number of divisors than any number smaller than itself. Given a positive integer b, your program should output the largest antiprime that is less than or equal...
number thoery
just need 2 answered
2. Let n be a positive integer. Denote the number of positive integers less than n and rela- tively prime to n by p(n). Let a, b be positive integers such that ged(a,n) god(b,n)-1 Consider the set s, = {(a), (ba), (ba), ) (see Prollern 1). Let s-A]. Show that slp(n). 1. Let a, b, c, and n be positive integers such that gcd(a, n) = gcd(b, n) = gcd(c, n) = 1 If...
2. Let L-M M): 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 [5 marks] b) Is L Turing-recognisable? Justify your answer with an informal argument. c) Prove that L is undecidable. (Hint: use Rice's theorem.) [20 marks] 20 marks] d) Bonus: Justify with a formal proof your answer to b).
2. Let L-M M): M is a Turing machine that accepts at...
Most questions answered within 3 hours.
-
Red light of wavelength 675 nm is incident on a slit of width
4.56 × 10−6...
asked 8 minutes ago -
An object 4.0 mm high is on the optical axis of two lenses with
focal lengths...
asked 4 minutes ago -
Suppose that each team in a league has a demand curve for
generic advertising (a league-wide...
asked 4 minutes ago -
1. The WJC purchases denim. The avg. daily demand of
western is 1000 yards and the...
asked 13 minutes ago -
Memory Allocation
a) Is it possible to have both internal and external
fragmentation with fixed partition...
asked 13 minutes ago -
Steven can afford car payments of $300 a month for 72 months.
The bank will lend...
asked 29 minutes ago -
Embedded
System..
1.
Analyze
the instruction
sets below.
LDR R1, [R0,
#0x08]
SUB R1, R1,
R2,...
asked 34 minutes ago -
Use proper sentence structure to communicate clearly.
Choose the correct sentence structure in each of the...
asked 34 minutes ago -
There are investors who claim they only invest in companies with
great products and outstanding management,...
asked 36 minutes ago -
what is employee/ employer relations ?
why is Employee/ Employer relation is important in the context...
asked 55 minutes ago -
Explain the relationship between tests of acquisition and
payment cycle and tests of accounts payable. Give...
asked 53 minutes ago -
A hot-air balloon is descending with a velocity of (−2.00m/s)y^.
A champagne bottle is opened to...
asked 1 hour ago