CECS 329 Final

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/60

encourage image

There's no tags or description

Looks like no tags are added yet.

61 Terms

1
New cards

a. |N| = |Q| < |R|

How are the cardinalities of the sets N of natural numbers, Q of rational numbers, and R of real numbers related to each other?

a. |N| = |Q| < |R|

b. |N| < |Q| = |R|

c. |N| = |Q| = |R|

d. |N| < |Q| < |R|

2
New cards

b. |N| = |2N|

Which statement about the cardinalities of the set N of natural numbers and the set 2N of even natural numbers is correct?

a. |N| < |2N|

b. |N| = |2N|

c. |N| > |2N|

d. The cardinalities |N| and |2N| are incomparable

3
New cards

a. |A| < |P(A)|

Which statement about the cardinalities of a set A and its power set P(A) is correct?

a. |A| < |P(A)|

b. |A| = |P(A)|

c. |A| > |P(A)|

d. The cardinalities |A| and |P(A)| are incomparable

4
New cards

a. Regular expression

Match the recognizer with the generator:

DFA

a. Regular expression

b. Context free grammar

5
New cards

a. Regular expression

Match the recognizer with the generator:

NFA

a. Regular expression

b. Context free grammar

6
New cards

b. Context free grammar

Match the recognizer with the generator:

PDA

a. Regular expression

b. Context free grammar

7
New cards

a. ∑ is a non-empty, finite set

What is the definition of an alphabet ∑?

a. ∑ is a non-empty, finite set

b. ∑ is a finite set

c. ∑ is a non-empty set

d. ∑ is a set

8
New cards

b. A set of strings over a finite alphabet

What is a formal language?

a. A programming language with strict syntax rules

b. A set of strings over a finite alphabet

c. A method of communication used in formal settings

d. A language with an infinite number of grammar rules

e. A mathematical function that computes string values

9
New cards

c. Production rules with a single non-terminal on the left-hand side

What characterizes a context-free grammar?

a. Production rules where each side can contain any string of terminals and non-terminals

b. Grammar that can generate all possible strings over its alphabet

c. Production rules with a single non-terminal on the left-hand side

d. Grammar that requires context to interpret its strings

e. Rules that allow for direct left recursion only

10
New cards

b. Tape

Which of the following is not a component of a pushdown automaton?

a. Stack

b. Tape

c. State

d. Input alphabet

e. Transition function

11
New cards

c. It can be recognized by a deterministic finite automaton

What is the defining feature of a regular language?

a. It can be recognized by a pushdown automaton

b. It can be generated by a context-free grammar

c. It can be recognized by a deterministic finite automaton

d. It can be recognized by a Turing machine

e. it can be generated by a non-deterministic automaton

12
New cards

b. ∃k1 > ∃k2 > 0∃m0∀n > n0: k1g(n) ≤ f(n) ≤ k2g(n)

Match the Bachmann-Landau asymptotic notation with the correct definition:

a. ∃k > 0∃n0∀n > n0: |f(n)| ≤ k g(n)

b. ∃k1 > ∃k2 > 0∃m0∀n > n0: k1g(n) ≤ f(n) ≤ k2g(n)

c. ∃k > 0∃n0∀n > n0: f(n) ≥ k g(n)

d. ∀k > 0∃n0∀n > n0: |f(n)| < k g(n)

f(n) ∈ θ(g(n)) (average case)

13
New cards

a. ∃k > 0∃n0∀n > n0: |f(n)| ≤ k g(n)

Match the Bachmann-Landau asymptotic notation with the correct definition:

a. ∃k > 0∃n0∀n > n0: |f(n)| ≤ k g(n)

b. ∃k1 > ∃k2 > 0∃m0∀n > n0: k1g(n) ≤ f(n) ≤ k2g(n)

c. ∃k > 0∃n0∀n > n0: f(n) ≥ k g(n)

d. ∀k > 0∃n0∀n > n0: |f(n)| < k g(n)

f(n) ∈ O(g(n)) (worst case)

14
New cards

d. ∀k > 0∃n0∀n > n0: |f(n)| < k g(n)

Match the Bachmann-Landau asymptotic notation with the correct definition:

a. ∃k > 0∃n0∀n > n0: |f(n)| ≤ k g(n)

b. ∃k1 > ∃k2 > 0∃m0∀n > n0: k1g(n) ≤ f(n) ≤ k2g(n)

c. ∃k > 0∃n0∀n > n0: f(n) ≥ k g(n)

d. ∀k > 0∃n0∀n > n0: |f(n)| < k g(n)

f(n) ∈ o(g(n)) (loose upper bound)

15
New cards

c. ∃k > 0∃n0∀n > n0: f(n) ≥ k g(n)

Match the Bachmann-Landau asymptotic notation with the correct definition:

a. ∃k > 0∃n0∀n > n0: |f(n)| ≤ k g(n)

b. ∃k1 > ∃k2 > 0∃m0∀n > n0: k1g(n) ≤ f(n) ≤ k2g(n)

c. ∃k > 0∃n0∀n > n0: f(n) ≥ k g(n)

d. ∀k > 0∃n0∀n > n0: |f(n)| < k g(n)

f(n) ∈ Ω(g(n)) (best case)

16
New cards

a. P ⊆ NP

What are the known relationships between the complexity classes N and NP?

a. P ⊆ NP

b. NP ⊆ P

c. P = NP

d. P ≠ NP

17
New cards

a. Yes, because a DFA reads one input symbol per state transition.

Are all regular languages in the complexity class P?

a. Yes, because a DFA reads one input symbol per state transition.

b. No, because an NFA could take exponential time to accept.

c. No, because a DFA reads one input symbol per state transition.

d. No, because a PDA might not halt.

18
New cards

a. P = All languages where we can test membership quickly

NP = All languages where we can verify membership quickly (given a short certificate)

How can we best describe the complexity classes P and NP informally?

a. P = All languages where we can test membership quickly

NP = All languages where we can verify membership quickly (given a short certificate)

b. P = All languages where we can test membership quickly

NP = All languages where we can guess membership quickly (given a short certificate)

c. P = All languages where we cannot test membership quickly

NP = All languages where we can verify membership quickly (given a short certificate)

d. P = All languages where we can guess membership quickly

NP = All languages where we can verify membership quickly (given a short certificate)

19
New cards

All of the above are correct.

a. multi-tape TMs

b. multi-dimensional Turing Machines

c. random access machines (RAM)

d. cellular automata

Two models of computation are polynomial related if each can simulate the other with a polynomial overhead, i.e. if the computation takes t(n) time on one model it may take t^k(n) time on the other model, for some k. Which of the following are polynomially related to a 1-tape Turing Machine?

a. multi-tape TMs

b. multi-dimensional Turing Machines

c. random access machines (RAM)

d. cellular automata

20
New cards

b. Cantor's diagonal argument

Alan Turing proved the undecidability of the halting problem. Which proof technique from set theory did inspire Turing?

a. Feynman's technique

b. Cantor's diagonal argument

c. Zorn's lemma

d. Newton's method

21
New cards

b. Acceptance problem for DFAs Adfa = {

c. Acceptance problem for NFAs Anfa = {

d. Equivalence problem for DFAs EQdfa = {

Which of the following languages are decidable?

a. Acceptance problem for TMs Atm = {

b. Acceptance problem for DFAs Adfa = {

c. Acceptance problem for NFAs Anfa = {

d. Equivalence problem for DFAs EQdfa = {

22
New cards

d. Any real-world computation can be translated into an equivalent computation performed by a Turing machine.

What does the Church-Turing-Thesis claim?

a. The λ-calculus can compute more than the Turing machine.

b. The Halting-problem of the Turing machine is undecidable.

c. The Turing machine can compute more than the λ-calculus.

d. Any real-world computation can be translated into an equivalent computation performed by a Turing machine.

23
New cards

a. True

Decidability of languages does not depend on the model of computation.

a. True

b. False

c. This is an open problem

24
New cards

b. Not necessarily. The time complexity might be O(n^k) with a very large value for k.

Languages in P can be efficiently decided.

a. Yes, that's the meaning of the class P.

b. Not necessarily. The time complexity might be O(n^k) with a very large value for k.

c. Not at all, problems in P generally have a high time complexity.

25
New cards

a. All regular languages are in the complexity class P.

c. All languages in P are decidable.

d. All languages in P are T-recognizable

Which of the following statements are correct:

a. All regular languages are in the complexity class P.

b. All decidable languages are in the complexity class P.

c. All languages in P are decidable.

d. All langiages in P are T-recognizable

26
New cards

a. 10011000

What is the output (on the tape) of ... M on input 10010111 where

M = (Q, ∑, Γ, δ, q0, qacc, q...) with

states Q = {right, carry, done},

input alphabet Σ = {1, 0},

tape alphabet Γ = {1, 0, ' '}

...

a. 10011000

b. 10010110

c. 01100111

d. 01101001

e. 10011010

f. 10011001

27
New cards

a.Yes

Is the complexity class P closed under union, i.e. does L1 ∈ P and L2 ∈ P imply that L1 ∪ L2 ∈ P?'

a.Yes

b. No

c. This is unknown

28
New cards

a. 2n ∈ O(n)

c. nlogn ∈ O(n^2)

d. 3^n ∈ 2^O(n)

Which of the following are true?

a. 2n ∈ O(n)

b. n^2 ∈ O(n)

c. nlogn ∈ O(n^2)

d. 3^n ∈ 2^O(n)

29
New cards

c. s^2 = (0^p)(1^p)(0^p)(1^p) ∈ F

Recall the pumping lemma for CFLs: For every CFL A there is a p ∈ N such that if s ∈ A and |s| ≥ p then s = uvxyz where

1.) u(v^i)x(y^i)z ∈ A for all i ≥ 0

2) vy ≠ ε

3) |vwy| ≤ p

Let Σ = {0, 1} and F = {ww|w ∈ Σ*}. In order to show that F is not context free, which value should we use for the3 string s to find a contradiction?

a. S0 = (0^p)(1^p) ∈ F

b. S1 = (0^p)(10)^p1 ∈ F

c. s^2 = (0^p)(1^p)(0^p)(1^p) ∈ F

30
New cards

????

???

31
New cards

False

Context free languages are closed under intersection

a. True

b. False

32
New cards

d. {(a^k)(b^k)|k ∈ N0}

Match the language with the smallest class it's contained in.

a. {a, b, c}

b. {

c. {a^k|k ∈ N0}

d. {(a^k)(b^k)|k ∈ N0}

e. {(a^k)(b^k)(c^k)|k ∈ N0}

Context Free

33
New cards

e. {(a^k)(b^k)(c^k)|k ∈ N0}

Match the language with the smallest class it's contained in.

a. {a, b, c}

b. {

c. {a^k|k ∈ N0}

d. {(a^k)(b^k)|k ∈ N0}

e. {(a^k)(b^k)(c^k)|k ∈ N0}

Decidable

34
New cards

a. {a, b, c}

Match the language with the smallest class it's contained in.

a. {a, b, c}

b. {

c. {a^k|k ∈ N0}

d. {(a^k)(b^k)|k ∈ N0}

e. {(a^k)(b^k)(c^k)|k ∈ N0}

Finite

35
New cards

c. {a^k|k ∈ N0}

Match the language with the smallest class it's contained in.

a. {a, b, c}

b. {

c. {a^k|k ∈ N0}

d. {(a^k)(b^k)|k ∈ N0}

e. {(a^k)(b^k)(c^k)|k ∈ N0}

Regular

36
New cards

b. {

Match the language with the smallest class it's contained in.

a. {a, b, c}

b. {

c. {a^k|k ∈ N0}

d. {(a^k)(b^k)|k ∈ N0}

e. {(a^k)(b^k)(c^k)|k ∈ N0}

T-Recognizable

37
New cards

d. S -> a | b | (S) | S+S

Provide a context free grammar for the language of all well-bracketed expressions over the alphabet ∑ = {(, ), a, b, +} where the symbol + is used as an infix binary operator.

valid.

a

a + b

(a + b)

a + a + b

(a + b) + (a + b)

((((a)))+b)+a+v

invalid.

()

a ++ b

a (+) b

(a + b

a + b)

a) + b

a. S -> aS | bS | (S + S)

b. S -> a+b | a+S | S+b | (S)

c. S -> aS + bS | (S)

d. S -> a | b | (S) | S+S

e. S -> a | b | (S) | (S+S)

38
New cards

b. if there is a computable function f : ∑* -> Γ* such that w ∈ A

A language A ⊆ ∑* is mapping reducible to a language B ⊆ Γ* and we write A ≤m B

a. There is a function f : ∑* -> Γ* computable in polynomial time such that w ∈ A

b. if there is a computable function f : ∑* -> Γ* such that w ∈ A

c. If there is a computable function f : ∑* -> Γ* such that w ∈ A

39
New cards

a. All the other options are correct.

Let ∑ be an alphabet. A language A ⊆ ∑* is called regular if there is a finite automaton M such that...

a. All the other options are correct.

b. A is the language of M

c. M recognizes A

d. A = L(m).

40
New cards

d. True

Regular languages are closed under union and intersection

a. This is unknown

b. False

c. This depends on the language

d. True

41
New cards

d. (0 u 1)* ⋅ 1 ⋅ 1 ⋅ (0 u 1)*

Write the language of all sequences of characters from ∑ = {0, 1} that contain two consecutive 1's as a regular expression.

a. (o u 1)* ⋅ (1 ⋅ 1)* ⋅ (0 u 1)*

b. 0* ⋅ 1 ⋅ 1 ⋅ 0*

c. (0 u 1)* u 1 u 1 u (0 ⋅ 1)*

d. (0 u 1)* ⋅ 1 ⋅ 1 ⋅ (0 u 1)*

42
New cards

a. No

All languages are regular.

a. No

b. Yes

c. This is still an open problem

43
New cards

c. ... prove that a language is not regular.

The pumping Lemma can be used to...

a. ... prove that DFAs are equivalent to NFAs.

b. ... prove that a language is regular.

c. ... prove that a language is not regular.

44
New cards

c. Yes, they all recognize regular languages.

GNFAs, NFAs, and DFAs are all equivalent, i.e. they all recognize the same class of languages

a. No, NFAs can recognize more languages than DFAs.

b. No, GNFAs can recognize more languages than NFAs.

c. Yes, they all recognize regular languages.

d. No, GNFAs can recognize more languages than DFAs.

45
New cards

b. No

Are all context free languages regular?

a. Yes

b. No

46
New cards

c. C1

Which of these are valid Context Free Grammars?

C1: S -> RR

R -> 0R1R | ε

C2: S -> 0R1R

OR -> 0R1 | ε

a. Both C1 and C2

b. Neither

c. C1

d. C2

47
New cards

b. {(0^k)(1^k) | k ∈ N}

Which of the following languages is context free but not regular

a. {0, 1}*

b. {(0^k)(1^k) | k ∈ N}

c. {0, 1}*11{0, 1}*

48
New cards

b. Adfa = {

c. Anfa = {

d. EQdfa = {

Which of the following languages are decidable?

a. Aim = {

b. Adfa = {

c. Anfa = {

d. EQdfa = {

49
New cards

b. A theoretical machine to model and reason about computation.

What is a Turing machine?

a. An early computing device invented by Alan Turing.

b. A theoretical machine to model and reason about computation.

c. A device invented by Alan Turing to discriminate humans from computers.

d. A machine created by Alan Turing to decipher Enigma codes.

50
New cards

c. True

Decidability of languages does not depend on the model of computation.

a. This is an open question

b. False

c. True

51
New cards

b. Yes, but it is equivalent for all reasonable deterministic models of computation.

The complexity class P does depend on the model of computation.

a. No, it doesn't

b. Yes, but it is equivalent for all reasonable deterministic models of computation.

52
New cards

c. Not necessarily. The time complexity might be O(n^k) within a very large value for k.

Languages in P can be efficiently decided.

a. Yes, that's the meaning of the class P

b. Not at all, problems in P generally have a high time complexity.

c. Not necessarily. The time complexity might be O(n^k) within a very large value for k.

53
New cards

a. All languages in P are T-recognizable

c. All languages in P are decidable.

d. All regular languages are in the complexity class P.

Which of the following statements are correct:

a. All languages in P are T-recognizable

b. All decidable languages are in the complexity class P.

c. All languages in P are decidable.

d. All regular languages are in the complexity class P.

54
New cards

a. P ⊆ NP

What is the known relationship between the complexity classes P and NP?

a. P ⊆ NP

b. NP ⊆ P

c. P = NP

d. P ≠ NP

55
New cards

d. if there is a computable function f: ∑* -> Γ* such that w ∈ A

What is the definition of mapping reducibility (also called many-one reducibility)?

Th language of A ⊆ ∑* is mapping reducible to the language B ⊆ Γ* and we write A ≤m B

a. if there is a computable function f: Γ* -> ∑* such that w ∈ A

b. if there is a computable function f: ∑* -> Γ* such that w ∈ B

c. if there is a computable function f: Γ* -> ∑* such that w ∈ B

d. if there is a computable function f: ∑* -> Γ* such that w ∈ A

56
New cards

d. Yes, because we need at least one computation step to write into a new memory cell.

Is it true that TIME(t(n)) ⊆ SPACE(t(n))?

a. Not necessarily, this is yet unknown.

b. No, time and space complexity are unrelated

c. Yes, because the tape of a Turing machine has a fixed size.

d. Yes, because we need at least one computation step to write into a new memory cell.

57
New cards

b. B is in NP and any language A in NP can be polynomially reduced to B.

A language B is NP-complete iff

a. B is not in NP and no language A in NP can be polynomially reduced to B.

b. B is in NP and any language A in NP can be polynomially reduced to B.

c. B is in NP and no language A in NP can be polynomially reduced to B.

d. B is not in NP and any language A in NP can be polynomially reduced to B.

58
New cards

a. SAT (Boolean Satisfiability)

b. 3-SAT (3-CNF Boolean Satisfiability)

Which of these languages are NP-Complete?

a. SAT (Boolean Satisfiability)

b. 3-SAT (3-CNF Boolean Satisfiability)

c. PATH (Path Problem)

d. HALT (Halting Problem)

59
New cards

a. No

Is the following formula satisfiable?

(x V y) ^ (x v not(y)) ^ (not(x) v y) ^ (not(x) v not(y))

a. No

b. Yes

60
New cards

b. Yes, because a TM that uses t(n) tape cells cannot use more than 2^O(t(n)) time without repeating a configuration and thus looping and not halting.

Is SPACE(t(n)) ⊆ TIME(2^O(t(n)))?

a. No, time and space complexity are unrelated.

b. Yes, because a TM that uses t(n) tape cells cannot use more than 2^O(t(n)) time without repeating a configuration and thus looping and not halting.

c. This in yet unknown.

61
New cards

b. SAT (Boolean Satisfiability)

d. 3-SAT (3-CNF Boolean Satisfiability)

Which of these languages are NP-Complete?

a. HALT (Halting Problem)

b. SAT (Boolean Satisfiability)

c. PATH (Path Problem)

d. 3-SAT (3-CNF Boolean Satisfiability)