Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 0: Q7E (page 1)

Question: Let B be the set of all infinite sequences over {0 , 1}. Show that B is uncountable using a proof by diagonalization.

Short Answer

Expert verified

Answer:

For the set set of βall infinite sequences over{0 , 1} , in which βis uncountable is proved by diagonalization.

Step by step solution

01

Diagonalization

Diagonalization is a technique to demonstrate that there are some languages that cannot be decided by a Turing machine. This is used as a way of showing that the (infinite) set of real numbers is larger than the (infinite) set of integers.

02

proof that sequence is uncountable.

Each element in is an infinite sequence b1,b2...........where eachbi∈0,1 suppose is countable. Then define a correspondence F between N=1,2,3......and β. Specifically for f(n)=b1,b2........... .

Now define infinite sequence that isc=c1,c2,c3,..........∈β ,set βset of all infinite sequences over0,1 , in which is uncountablewhere the opposite of the ith bit is and here the function is defined asf(n)=b1,b2........... an infinite sequence is given as below,

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

Give a counter example to show that the following construction fails to prove that the class of context-free languages is closed under star. Let A be a CFL G=(V,∑,R,S)that is generated by the CFG . Add the new rule S→SSand call the resulting grammar. This grammar is supposed to generate A* .

For each part, give a relation that satisfies the condition.

  1. Reflexive and symmetric but not transitive
  2. Reflexive and transitive but not symmetric
  3. Symmetric and transitive but not reflexive

Give a counter example to show that the following construction fails to prove that the class of context-free languages is closed under star. Let A be a CFL that is generated by the CFG G=(V,∈,R,S). Add the new ruleS→SS and call the resulting grammar. This grammar is supposed to generate A*.

A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end and read only at the right-hand end. Each write operation (we’ll call it a push) adds a symbol to the left-hand end of the queue and each read operation (we’ll call it a pull) reads and removes a symbol at the right-hand end. As with a PDA, the input is placed on a separate read-only input tape, and the head on the input tape can move only from left to right. The input tape contains a cell with a blank symbol following the input, so that the end of the input can be detected. A queue automaton accepts its input by entering a special accept state at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turing-recognizable.

Let MODEXP={ha,b,c,pi|a,b,c,andpare positive binary integers such that ab≡cmodp}.

Show that MODEXP∈P. (Note that the most obvious algorithm doesn’t run in polynomial time. Hint: Try it first where b is a power of 2 .)
See all solutions

Recommended explanations on Computer Science Textbooks

Issues in Computer Science

Read Explanation

Algorithms in Computer Science

Read Explanation

Computer Systems

Read Explanation

Computer Programming

Read Explanation

Theory of Computation

Read Explanation

Big Data

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