CSC 240

Lab 13 - Computational Problem Classifier

In this assignment you will take a list of languages and classify them by type.

Assignment

For each of the following languages, choose it's location in the family of language types we've discussed this semester:

Languages

1. A = { <TM> | <TM> is a Turing Machine and |ℒ(TM)| ≥ 2}
2. B = { <TM> | <TM> is a Turing Machine and |ℒ(TM)| = 2}
3. C = { aⁿbⁿ | n ∈ ℕ and n > 100}
4. D = { aⁿbⁿ | n ∈ ℕ and n < 100}
5. E = { aⁿ | n is a multiple of 5}
6. F = { x* }
7. G = { w-w | w ∈ {0,1} }
8. H = { w*-w* | w ∈ {0,1} }

Hints

• Think about what it means for a language to belong to a particular category.

• Remember, we can build a verifier for any language in RE, meaning given an input string and some evidence, we can build a Turing Machine that will verify that the input string belongs to the language.

• Likewise, we can build a decider for any language in R, meaning given an input string, we can conclusively decide if the input belongs to the language or not.

• Finally, regular languages require finite amounts of memory.

• You should specify the most descriptive class for each language. If a language is regular, that means it is also context free, R, and RE, but you should only specify "Regular".

Submission

To submit your assignment, write your answers for each language and upload it as a word doc or pdf to mySVU.