Homework Answers
2. Proof:
Let's say ? is the constant of the pumping lemma, and let's consider ? = ??N?N ∈ ? and |?| = 2?+1 ≥ ?. By the lemma, it can be written ? = ???, such that |??| ≤ ? with ? ≠ ? such that for all ?≥0 it is ??k? ∈ ?.
Now ? must be composed of only one symbol (in this case, as |??|≤?, it has to be only ? or some ?s) as otherwise ??k? for ?>1 isn't of the right form (?s followed by ?s followed by ?s). Now ?=?, ?=? is impossible, because in that case we have ??0? = ?N?N ∉ ?. But ? just ?s with ?≠1 gives a string with number of ?s and ?s different, thus not in ?. No division into ?,?,? works, the language fails the pumping lemma. Hence it can't be regular.
Hope this helped. Please do upvote and if there are any queries please ask in comments section.
Add Answer to:
2. Prove that {a"6"c" |m,n0}is not a regular language. Answer: 3. Let L = { M...
3. Let L= {MM is a Turing machine and L(M) is empty), where L(M) is the...
3. Let L= {MM is a Turing machine and L(M) is empty), where L(M) is the language accepted by M. Prove L is undecidable by finding a reduction from Arm to it, where Arm={<M,w>| M is a Turing machine and M accepts w}
please answer and I will rate! 3. Let L = {M M is a Turing machine...
please answer and I will rate!
3. Let L = {M M is a Turing machine and L(M) is empty), where L(M) is the language accepted by M. Prove Lis undecidable by finding a reduction from Arm to it, where Ayv-<<MwM is a Turing machine and M accepts w). Answer:
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...
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...
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...
(3) Prove that the following language is undecidable L {< M, w> M accepts exactly three...
(3) Prove that the following language is undecidable L {< M, w> M accepts exactly three strings }. Use a reduction from ArM
6. (10 points) Prove that the language L = {< M 1 , M 2 >: M, , M 2 are T M s and L(M-) = L(M 2)) is undecidable....
6. (10 points) Prove that the language L = {< M 1 , M 2 >: M, , M 2 are T M s and L(M-) = L(M 2)) is undecidable.
6. (10 points) Prove that the language L = {: M, , M 2 are T M s and L(M-) = L(M 2)) is undecidable.
3. Let L-{(M, q》 | M is a Turing machine and q is a state in...
3. Let L-{(M, q》 | M is a Turing machine and q is a state in M such that: there is at least one input string w such that M executed on w enters state q). Side note: In the real world, you can think of this as a question about finding "dead code" in a program. The question is: for a given line of code in your program, is there an input that will make the program execute that...
A Turing machine M decides a language L is M: Group of answer choices All of...
A Turing machine M decides a language L is M: Group of answer choices All of these apply. Accepts all strings in L and M rejects all strings not in L. Accepts some strings in L and M rejects some strings not in L. Accepts all strings in L that are recognizable.
I'm not sure how to answer this problem. Can someone help me with this. thanks 5. Let M be the Turing machine BIBR 9 9 ala R a) Give a regular expression for L(M. b) Using the techniques from The...
I'm not sure how to answer this problem. Can someone help me
with this. thanks
5. Let M be the Turing machine BIBR 9 9 ala R a) Give a regular expression for L(M. b) Using the techniques from Theorem 10.1.3, give the rules of an unrestricted gram- mar G that accepts L(M. c) Trace the computation of M when run with input bab and give the corresponding derivation in G.
5. Let M be the Turing machine BIBR 9...
3. Let L= {MM is a Turing machine and L(M) is empty), where L(M) is the language accepted by M. Prove L is undecidable by finding a reduction from Arm to it, where Arm={<M,w>| M is a Turing machine and M accepts w}
please answer and I will rate!
3. Let L = {M M is a Turing machine and L(M) is empty), where L(M) is the language accepted by M. Prove Lis undecidable by finding a reduction from Arm to it, where Ayv-<<MwM is a Turing machine and M accepts w). Answer:
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...
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...
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...
(3) Prove that the following language is undecidable L {< M, w> M accepts exactly three strings }. Use a reduction from ArM
6. (10 points) Prove that the language L = {< M 1 , M 2 >: M, , M 2 are T M s and L(M-) = L(M 2)) is undecidable.
6. (10 points) Prove that the language L = {: M, , M 2 are T M s and L(M-) = L(M 2)) is undecidable.
3. Let L-{(M, q》 | M is a Turing machine and q is a state in M such that: there is at least one input string w such that M executed on w enters state q). Side note: In the real world, you can think of this as a question about finding "dead code" in a program. The question is: for a given line of code in your program, is there an input that will make the program execute that...
I'm not sure how to answer this problem. Can someone help me
with this. thanks
5. Let M be the Turing machine BIBR 9 9 ala R a) Give a regular expression for L(M. b) Using the techniques from Theorem 10.1.3, give the rules of an unrestricted gram- mar G that accepts L(M. c) Trace the computation of M when run with input bab and give the corresponding derivation in G.
5. Let M be the Turing machine BIBR 9...
Most questions answered within 3 hours.
-
Please explain steps:
An 80 kg swimmer steps off a platform 10 m above the water...
asked 9 minutes ago -
A lottery exists where balls numbered 1 to 17 are placed in an
urn. To win,...
asked 12 minutes ago -
26) Briefly describe, using words or simple diagrams, the
chemiosmotic theory for coupling oxidation to phosphorylation...
asked 2 hours ago -
Suppose that XX is a random variable with mean 16 and standard
deviation 5 . Also...
asked 2 hours ago -
Calculate the number density of argon gas at a temperature of
24C and a pressure of...
asked 6 hours ago -
Alternative
Classification
How to Estimate
Probabilities from Data? ( For continuous Attributes)
And How to generate...
asked 6 hours ago -
An explosion breaks a 20.0-kg object into three parts. The
object is initially moving at a...
asked 7 hours ago -
Calculate the approximate number of residues of Rubisco, which
is involved in carbon fixation in plants,...
asked 8 hours ago -
Other decisions about scientific claims can have a much broader
impact.ENERGYarrow-10x10.png, environment, health, security - all...
asked 8 hours ago -
I need to write a research paper and work cited about this
topic: The United States...
asked 9 hours ago -
Hello! I was wondering if I could have some help?
If the vapor pressure of carvone...
asked 9 hours ago -
An economist wants to estimate the mean per capita income (in
thousands of dollars) for a...
asked 10 hours ago