Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Q29E

Page 898

Which of the following problems is a decision problem?

a)What is the smallest prime greater than n?

b)Is a graph G bipartite?

c)Given a set of strings, is there a finite-state automaton that recognizes this set of strings?

d)Given a checkerboard and a particular type of polyomino (see Section 1.8), can this checkerboard be tiled using polyominoes of this type?

Q29SE

Page 901

Construct a Turing machine that computes the function f(n1,n2)=max(n1,n2).

Q2E

Page 887

Describe in words the strings in each of these regular sets.

  1. 001
  2. (01)
  3. 01001
  4. 0(110)
  5. (101)
  6. (01)11

Q2E

Page 864

Give the state tables for the finite-state machines with these state diagrams.

Q2E

Page 875

Show that if A is a set of strings, thenA=A=.

Q2E

Page 897

Let T be the Turing machine defined by the five tuples: (s0,0,s1,0,R),(s0,1,s1,0,L),(s0,B,s1,1,R),(s1,0,s2,1,R),(s1,1,s1,1,R),(s1,B,s2,0,R), and (s2,B,s3,0,R). For each of these initial tapes, determine the final tape when T halts, assuming that T begins in initial position.

a)

... B B 0 1 0 1 B B ...

b)

... B B 1 1 1 B B B ...

c)

... B B 0 0 B 0 0 B ...

d)

.... B B B B B B B B ...

Q2E

Page 856

Find five other valid sentences, besides those given in Exercise 1.

Q2RE

Page 900

a)what is the language generated by a phrase-structure grammar G?

b)What is the language generated by the grammar Gwith vocabulary{S,0,1}, set of terminals T= {0,1}, starting symbol S, and productions S→000S, S→1?

c)Give a phrase-structure grammar that generates the set {01n|n=0,1,2....}.

Q2SE

Page 901

Find a phrase-structure grammar that generates the set {02nn0}.

Q30E

Page 876

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that begin with 0 or with 11.

Access millions of textbook solutions in one place

  • Access over 3 million high quality textbook solutions
  • Access our popular flashcard, quiz, mock-exam and notes features
  • Access our smart AI features to upgrade your learning
Get Vaia Premium now
Access millions of textbook solutions in one place

Recommended explanations on Math Textbooks