CSCI 6420
Homework assignment 1

Due:Friday, January 15

Face-to-face students: Submit in class.

Online students: submit a scanned or typed homework by email, as an attachment.

1. Sipser, exercise 0.2 (a-f), page 25.

2. Sipser, exercise 0.3 (a-f), page 26.

3. You can think of a language as a computational problem. You can think of an integer as a string by reprenting it in standard (decimal) notation.

   Consider the following language.

   S = {n² | n is a nonnegative integer}

   That is, S is the set of all perfect squares.

   We have defined what it means for a language to be computable. Show that S is computable by describing an algorithm that solves S.