xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

数学代写-CSE 103

时间：2021-03-12

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

学霸联盟

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

学霸联盟