Show that L = {anbmanbm | n,m belongs to N} is Turing-recognisable, by precisely describing a...
Show that L = {anbmanbm | n,m belongs to N} is Turing-recognisable, by precisely describing a Turing machine M with L(M) = L.
Homework Answers
Let's go though it using an example aabbbaabbb
STAGE 1
- Mark one a as blank symbol: >abbbaabbb
- Any of the two
- Move right over all a's: a>bbbaabbb
- If b comes instead of a, go to STAGE 2 (by this time the string is >bbbxabbb)
- Move right over all b's and x's: abbb>aabbb
- Mark one a as x: abbbx>abbb
- Go to the left most and go to step 1
STAGE 2
- Move right on b's and x's, then mark one a as x and go to the left most: bbbxxbbb
- Mark one b as blank and go to the right most and mark one b as blank (bbxxbb, bxxb, xx)
- Do above as long as there are b's
- Once all b's are over, if string has only x's, accept
Add Answer to:
Show that L =
{anbmanbm | n,m belongs
to N} is Turing-recognisable, by precisely describing 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...
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...
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...
Problem 3: Turing Machine Models Turing-Recognisablity and Decidability [20] a. Show that an FA w...
Subject : Theory of Computation
Please answer , posting second time now cause nobody answered it
previously
Problem 3: Turing Machine Models Turing-Recognisablity and Decidability [20] a. Show that an FA with a FIFO queue is Turing universal (i.e equivalent in computational power to a Turing machine). You should regard this machine as being formally defined in a way that is very similar to a PDA, except that on each transition, instead of pushing and/or popping a character, the machine...
Let Show that L is undecidable L = {〈M) IM is a Turing Machine that accepts w whenever it accepts L = {〈M) IM is a Turing Machine that accepts w whenever it accepts
Let Show that L is undecidable L = {〈M) IM is a Turing Machine that accepts w whenever it accepts L = {〈M) IM is a Turing Machine that accepts w whenever it accepts
Design a DPDA M as a two-tape turing machine such that L(M) = {anbn : n>=0}
Design a DPDA M as a two-tape turing machine such that L(M) = {anbn : n>=0}
Let L = {0^n 1^n | n ≥ 0}. Draw the state diagram of a Turing...
Let L = {0^n 1^n | n ≥ 0}. Draw the state diagram of a Turing
machine deciding L= Σ∗\L(basically the complement of L), where Σ =
{0,1}, and Γ = {0,1,#,U}, and “\” is set subtraction.
I understand that the complement of L will be {0^n 1^m | n=!m} U
{(0 U 1)* 1 0 {0 U 1)*}.
How should I draw the state diagram with this?
Let L = {0"1" | n > 0}. Draw the state diagram...
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}
Use a Turing Reduction to show that the following language is undecidable. L={ | L(M) is...
Use a Turing Reduction to show that the following language is undecidable. L={ | L(M) is infinite}.
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 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-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...
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...
Subject : Theory of Computation
Please answer , posting second time now cause nobody answered it
previously
Problem 3: Turing Machine Models Turing-Recognisablity and Decidability [20] a. Show that an FA with a FIFO queue is Turing universal (i.e equivalent in computational power to a Turing machine). You should regard this machine as being formally defined in a way that is very similar to a PDA, except that on each transition, instead of pushing and/or popping a character, the machine...
Let L = {0^n 1^n | n ≥ 0}. Draw the state diagram of a Turing
machine deciding L= Σ∗\L(basically the complement of L), where Σ =
{0,1}, and Γ = {0,1,#,U}, and “\” is set subtraction.
I understand that the complement of L will be {0^n 1^m | n=!m} U
{(0 U 1)* 1 0 {0 U 1)*}.
How should I draw the state diagram with this?
Let L = {0"1" | n > 0}. Draw the state diagram...
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:
Most questions answered within 3 hours.
-
It costs Crane Company $28 of variable costs and $10.00 of
allocated fixed costs to produce...
asked 9 minutes ago -
Explain the following basis of electron configuration i) the
electron affinity of S is +200kJ mol-1
asked 19 minutes ago -
Determine the pH of a 0.10 M
CH3NH3Cl solution.
(Kb
(CH3NH2) = 4.4 x 10-4)
2.18...
asked 27 minutes ago -
Asolid metal sphere with radius 0.470 m carries a net charge of
0.200 nC .
Part...
asked 23 minutes ago -
Determine the pH of a 0.0500 M KBr solution (using activity
coefficients when needed)
( please...
asked 25 minutes ago -
Bender's skateboards have the following manufacturing
expenses:
Direct Materials: $10/unit
Direct Labor: $8/unit
Rent: $10,000/month
Depreciation:...
asked 34 minutes ago -
9) A resistor is connected to a capacitor of 4 micro-farads
without a battery. The initial...
asked 42 minutes ago -
Via Gelato is a popular neighborhood gelato shop. The company
has provided the following cost formulas...
asked 1 hour ago -
The Williams have a stock they have held for over a year that
they believe is...
asked 2 hours ago -
11.53g sample of NaBr contains 22.34% Na by mass Considering
the law of constant composition how...
asked 3 hours ago -
Exercise 5-22A Complete the accounting cycle using receivable
transactions (LO5–1, 5–2, 5–4, 5–5, 5–7) [The following...
asked 3 hours ago -
Do you agree with the view that small businesses are more
vulnerable to employee theft because...
asked 3 hours ago