CSE 103 Computational Models Winter 2021
Midterm Exam, February 8, 2021
1. (10pts) What type of algorithmic problems are primarily considered in the study of compu-
tational models?
2. (10pts) Let Σ equal the alphabet {a}. 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.) {∅}
3. (10pts) From the definition of countably infinite prove that the set of numbers that are one
less than the square of an even positive integer is countably infinite.
4. (10pts) Given that the complement of any regular language is regular and that the intersection
of any two regular languages is regular, prove that the union of any two regular languages is
regular.
5. (10pts) Given that the union of any two regular languages is regular prove that the union of
any finite number of regular languages is regular.
6. (10pts) Prove that the union of an infinite number of regular languages is not necessarily
regular. You can use the fact that {0n1n | n ≥ 1} is not regular.
7. (10pts) Write the formal definition of regular language given in class.
8. (10pts) How can we prove a language is regular? List the ways covered in class.
9. (10pts) For what operations are regular languages closed?
10. (30pts) Consider the languages L1 = {x ∈ {0, 1}∗ | x contains at least two 0s } and L2 =
{x ∈ {0, 1}∗ | x contains an odd number of 1s } .
Give the state diagram for a DFA that recognizes L1. There should be no more than
three states. Label them 1, 2 and 3.
Give the state diagram for a DFA that recognizes L2. There should be no more than two
states. Label them A and B.
Use the product construction to build a DFA that recognizes the intersection of languages
L1 and L2. Clearly show you are using the product construction. You must show all the states
but you do not have to show the transition arrows for states that are not reachable.
11. (10pts)Given: Σ = {0, 1}, and the following definition of a language:
L = {w ∈ Σ∗| such that the number of 0 to 1 changes is equal to the number of 1 to 0 changes in w}
Show the state diagram for a DFA with out more than five states that recognizes L.
1
12. (10pts) Consider the language L = {x ∈ {a, b}∗ | number of ”a”s ≡ number of ”b”s mod 3}.
Show the state diagram for a DFA that recognizes L.
13. (10pts) How is an NFA (without -moves) different from a DFA? In each case of a difference
be sure to indicate both how a NFA works and how a DFA works.
14. (10pts) Show the state diagram for an -NFA that recognizes the language
L = {1n | n is a multiple of 7 or of 5}
15. (10pts) Show the state diagram for a NFA without moves that recognizes the same language
as the above -NFA.
16. (10pts) Show the state diagram for an NFA, without -moves and no more than three states,
that recognizes the language
L = {w ∈ {a, b}∗ | w ends with the two letters ab}
Label your states 1, 2 and 3 with 1 being the start state.
17. (10pts)Use the subset construction to build a DFA that recognizes the language recognized
by the above NFA. Clearly show your steps so that it is clear that you used the subset
construction. You must show all the states and indicate the accept states but you do not
have to show the transition arrows for states that are not reachable.
18. (10pts) In regards to the subset construction what is exponential blowup? Is it possible that
there may be an algorithm that can avoid it in all cases? Justify your answer.
19. (50pts)Given: Σ = {0, 1}, write regular expressions for the following languages:
Strings that have a length of at most three.
Strings that have a length divisible by 3.
Strings that have no more than two 0s.
Strings that do not end with 11.
Strings that consist of only 1s and interpreted as a binary number are even.
20. (10pts)What does Kleene’s Theorem state about languages that can be defined with DFAs
and languages that can be denoted with regular expressions?
2

































































学霸联盟