5.1.4. Valid sequencing of elements in the set Π*

Try these first

1. 1.

   Define what a countable set is.

   Hint

   Think about how we can list items.

2. 2.

   What is an example of a finite alphabet?

   Hint

   Consider any limited set of characters.

3. 3.

   What characterizes a countable set?

   • Can be infinite
   • Can be matched with natural numbers
   • Limited to three elements

   Hint

   Think about how we arrange or list elements.

4. 4.

   Is Π* finite or infinite?

   • True
   • False

   Hint

   Consider the growing number of strings.

5. 5.

   Given an alphabet of characters {x, y, z}, enumerate all strings of length 2 and 3, discussing your sequence strategy.

   Hint

   Start with the shorter length and iterate.

6. 6.

   Explain how you can create a valid program from a basic structure. Show how the set of valid programs remains countable.

   Hint

   Think about building on existing valid structures.