xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

微信客服：xiaoxionga100

微信客服：ITCS521

数学代写-CMPS 130

时间：2021-02-08

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

2https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

5. (10pts) Prove that the complement of any regular language is a regular language.

4

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

13. (10pts) Prove that if the square of a natural number is even then the number must be even.

9

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

Powered by TCPDF (www.tcpdf.org)

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

2https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

5. (10pts) Prove that the complement of any regular language is a regular language.

4

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

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

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

13. (10pts) Prove that if the square of a natural number is even then the number must be even.

9

https://www.coursehero.com/file/75977651/cmps130s19midterm1pdf/

Th

is s

tud

y r

eso

urc

e w

as

sha

red

vi

a C

ou

rse

He

ro.

com

Powered by TCPDF (www.tcpdf.org)