MTH210

Tutorial 10

 Ryerson University

Computability and gcd

Readings

This tutorial covers material from sections 5.4, 7.5, and 3.8 of the textbook. In addition there are some extra optional pumping lemma questions (12.2). Page and exercise numbers are from the course textbook.

Tutorial 10

  1. p. 296 #11, 12, 13

  2. p. 454 #4, 15

  3. p. 455 #35, 37

  4. p.197 #16, 18

  5. p.197 #24
    Which is the better algorithm, this one or The Euclidean Algorithm? Why?

  6. Extra pumping lemma questions (optional).

    1. Use the pumping lemma to show that L = {ambncmax(m, n) | m, n ∈ N } is not regular.

    2. Use the pumping lemma to show that L = {0n + 0m = 0n+m | n, m ∈ N } over the alphabet { 0, +, = } is not regular.

This page is maintained by Peter Danziger.
Last modified Wednesday, 31-Mar-2010 12:05:54 EDT