CMPS 130 Computational Models Spring 2019
Midterm 1, April 22, 2019
NAME
ID. NUM.
Page 3 40 points
Page 4 10 points
Page 5 10 points
Page 6 30 points
Page 7 30 points
Page 8 40 points
Page 9 10 points
1
2
1. (10pts) What are decision problems and why is it reasonable to focus on them in the study
of computational models?
2. (10pts) Let A = {6, 5}, B = {5, 4, 9} and C = {9, 8, 7}.
Find the following sets:
a.) A ∪B
b.) C ∩ (B ∪A)
c.) A ∩B ∩C
d.) 2A
e.) A× (C −B)
3. (10pts) Let Σ equal the alphabet {a, b, c, d, e}. For each of the following sets indicate if its
cardinality is finite or infinite. If it is finite what is its cardinality and if it is not finite is it
countable or uncountable?
a.) Σ
b.) 2Σ
∗
c.) Σ∗
d.) 2Σ
e.) Ø
4. (10pts) Prove directly from the definition of countable that the even natural numbers are
countable.
3
5. (10pts) Prove that the complement of any regular language is a regular language.
4
6. (10pts) Given that the complement of any regular language is regular and that the intersection
of any two regular languages is regular, prove that if the set A is regular and the set B is
regular then the set A ∪B must be regular.
5
7. (30pts) Complete the following definitions:
A Deterministic Finite Automaton, DFA, is a structure M such that:
The extended transition function for M is recursively defined in terms of the transition
function as follows:
A string x ∈ Σ∗ is accepted by M if
The language accepted or recognized by M is
A language is by definition regular if
6
8. (20pts) Consider the language L = {x ∈ {0, 1}∗ | x contains at least three 1s } .
Give the state diagram for a DFA that recognizes L.
Give the formal description for the DFA above that recognizes L.
9. (10pts) Give the state diagram for a DFA that recognizes the language
{x ∈ {0, 1}∗ | x does NOT contain at least three 1s } .
7
10. (10pts) Give the state diagram for a DFA with no more than two states that recognizes the
strings over the alphabet {0, 1} that contain an odd number of 0s.
11. (10pts) Give the state diagram for a DFA with no more than two states that recognizes the
strings over the alphabet {0, 1} that end with 1.
12. (20pts) Use the product construction to build a DFA that recognizes the intersection of the
above two languages. Clearly show your steps so it is clear that you used the product con-
struction.
8
13. (10pts) Prove that if the square of a natural number is even then the number must be even.
9

欢迎咨询51作业君