Give an example of a language that is regular and PROVE that it is a member of the set of regular languages.
computer science
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.
