Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 0: Q18P (page 1)

Show that EQTM is recognizable by a Turing machine with an oracle for ATM.

Short Answer

Expert verified

The solution is given below.

Step by step solution

01

Turing Recognizable.

A language L is said to be Turing Recognizable if and only if there exist any Turing Machine (TM) which recognize it i.e. Turing Machine halt and accept strings belong to language and will reject or not halt on the input strings that doesn’t belong to language.

02

The proof is given below.

To prove above statement, we will assume an oracle Turing Machine T for ATM.

Let us also consider two Turing Machines P and Q such that they will be decider for TM T and T will be decider for ATM. This in turn makes ATM as Turing Recognizable for EQTM.

We will express above sentence as follow:

(P,w)∈ATM⇔T(M,w)∈EQTM

We will construct Turing Machine P and Q from above expression:

T = on inputP,w:string w will be made run on P

  • Construct TM P and Q such that:

⇒P= on input: Accept in all input

⇒ Q= on input: w run on P

If accepts at w, then accept for any input

  • Output: ‹P,Q›

Thus we can conclude that our assumed TM works as decider for ATM and so ATM will be decider for EQTM.

This proves that EQTM is recognizable by a Turing machine with an oracle for ATM .

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Question:Consider the algorithm MINIMIZE, which takes a DFA as input and outputs DFA .

MINIMIZE = “On input , where M=(Q,Σ,δ,q0,A) is a DFA:

1.Remove all states of G that are unreachable from the start state.

2. Construct the following undirected graph G whose nodes are the states of .

3. Place an edge in G connecting every accept state with every non accept state. Add additional edges as follows.

4. Repeat until no new edges are added to G :

5. For every pair of distinct states q and r of and every a∈Σ :

6. Add the edge (q,r) to G if δq,a,δr,a is an edge of G .

7. For each state q,let[q] be the collection of statesq={r∈Q|noedge joins q and r in G }.

8.Form a new DFA M'=Q',Σ,δ',q'0,A'where

Q'={[q]|q∈Q}(ifq=r,onlyoneofthemisinQ'),δ'(q,a)=[δq,a]foreveryq∈Qanda∈Σ,q00=[q0],andA0={[q]|q∈A}

9. Output ( M')”

a. Show that M and M' are equivalent.

b. Show that M0 is minimal—that is, no DFA with fewer states recognizes the same language. You may use the result of Problem 1.52 without proof.

c. Show that MINIMIZE operates in polynomial time.

Let D=w|wcontains an even number of ’s and an odd number of ’s and does not contain the substring ab}. Give a DFA with five states that recognizes Dand a regular expression that generates D.(Suggestion: Describe Dmore simply.)

Use the recursion theorem to give an alternative proof of Rice’s theorem in Problem 5.28.

Show that if G is a CFG in Chomsky normal form, then for any stringw∈L(G) of lengthn⩾1, exactly2n-1 steps are required for any derivation of w.

For each of the following languages, give two strings that are members and two strings that are not members—a total of four strings for each part. Assume the Σ=a,balpha-alphabet in all parts.

a.a*b*b.aba*bc.a*∪b*d.aaa*e.Σ*aΣ*bΣ*aΣ*f.aba∪babg.(ε∪a)bh.(a∪ba∪bb)Σ*
See all solutions

Recommended explanations on Computer Science Textbooks

Data Structures

Read Explanation

Computer Network

Read Explanation

Data Representation in Computer Science

Read Explanation

Issues in Computer Science

Read Explanation

Big Data

Read Explanation

Databases

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free