Description

2) (10 points) Give an example of a language that is regular and PROVE that it is a member of the set of regular languages. The alphabet for this language should be the first 1-3 distinct letters of your last name.

3) (20 points)

a) Give an example of a language that is context-free and PROVE that it is a member of the set of context-free languages. The
     alphabet for this language should be the first 2-3 distinct letters of your last name.

b) PROVE that this language is not a member of the set of regular languages.

4) (6 points) Give any example of a language that is Turing-recognizable, but not context-free. The alphabet for this language should be
                         the first 2-3 distinct letters of your last name.

5) (10 points) Give an example of a machine that can not be built. Explain why it can not be built. Why is this limitation significant to
                            our field? Remember that there are three parts to this question.

6) (30 points) Give the state machine and algorithm description of a Turing machine that accepts strings in PALINDROME with a #
                            in the middle of the string. The alphabet for this language should be the first 2 distinct letters of your last name.

7) (10 points) Explain why non-determinism has no effect on computability. Your answer should include the effect of non-determinism on both the set of regular languages and the set of Turing-recognizable languages.

8) (10 points) Explain how the Universal Turing Machine “bridges the gap” between a state machine that accepts a set of strings to a model for general computing. Hint: von Neumann extended the idea.

Bonus: (2 points) Give two examples of how the material in CMPS 479 can be used in the real world.