Flashcards CECS 329-Final

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

All other options are correct.

All languages are regular.

No

The Pumping Lemma can be used to

prove that a language is not regular

What does the Church-Turing-Thesis say?

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

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

c. The Halting-Problem of the Turing machine is undecidable.

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

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

Which of the following languages are decidable?

a. EQDFA = { | A and B are DFAs and L(A) = L(B)}

b. ADFA = { | B is a DFA and B accepts w}

c. ATM = { | M is a TM and M accepts w }

d. ANFA = { | B is a NFA and B accepts w}

a. EQDFA = { | A and B are DFAs and L(A) = L(B)}

b. ADFA = { | B is a DFA and B accepts w}

d. ANFA = { | B is a NFA and B accepts w}

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.

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

The complexity class P does depend on the model of computation

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

Languages in P can be efficiently decided

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

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

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

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

Which of the following statements are correct:

a. All languages in P are decidable

b. All regular languages are in the complexity class P

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

d. All languages in P are T-recognizable.

a. All languages in P are decidable

b. All regular languages are in the complexity class P

d. All languages in P are T-recognizable.

What is the definition of the Bachmann-Landau big O notation?

f(n)∈O(g(n))⟺

a. ∃k>0∀n0∃n>n0:|f(n)|≥kg(n)

b. ∀k>0∃n0∀n>n0:|f(n)|

c. ∃k>0∃n0∀n>n0:|f(n)|≤kg(n)

What are the known relationships between the complexity classes P and NP

a. NP ⊆ P

b. P ⊆ NP

c. P ≠ NP

d. P = NP

b. P ⊆ NP

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

The language A⊆Σ∗ is mapping reducible to the language B⊆Γ∗ and we write A≤mB

a. if there is a computable function f:Σ∗→Γ∗ such that w∈B⟺f(w)∈A.

b. if there is a computable function f:Γ∗→Σ∗ such that w∈B⟺f(w)∈A.

c. if there is a computable function f:Σ∗→Γ∗ such that w∈A⟺f(w)∈B.

d. if there is a computable function f:Γ∗→Σ∗ such that w∈A⟺f(w)∈B.

c. if there is a computable function f:Σ∗→Γ∗ such that w∈A⟺f(w)∈B.

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

a. No, time and space complecity are unrelated

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

c. Not necessarily, this is yet unknown

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

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

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 not 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 in NP and any language A in NP can be polynomially reduced to B.

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

Which of these languages are NP-Complete?

a. 3-SAT (3-CNF Boolean Satifiability)

b. HALT (Halting Problem)

c. PATH (Path Problem)

d. SAT (Boolean Satifiability)

a,d 3-SAT (3-CNF Boolean Satifiability), SAT (Boolean Satifiability)

What does NFA N1 do on input aab ?

Accept

Let A1 = {0k1 k2 l| k, l ≥ 0} (equal #s of 0s and 1s).

Let A2 = {0l1 k2 k| k, l ≥ 0} (equal #s of 1s and 2s).

Observe that PDAs can recognize A1 and A2 . What can we now conclude?

The class of CFLs is not closed under intersection.

A language A ⊆ Σ ∗ is polynomial time reducible to the language B ⊆ Γ ∗ and we write A ≤p B

a. if there is a computable function f: Σ∗ → Γ∗ such that w ∈ A

b. if there is a function f : Σ∗ → Γ∗ computable in polynomial time such that w ∈ A

c. if there is a polynomial f: Σ∗ → Γ∗ such that w ∈ A

d. if there is a function f: Σ∗ → Γ∗ such that w ∈ A

b. if there is a function f : Σ∗ → Γ∗ computable in polynomial time such that w ∈ A

If we would find a proof for SAT ∈ P then this would imply that

a. P ≠ NP

b. P ⊂ NP

c. P = NP

d. P ⊃ NP

c. P = NP

Are all regular languages in the complexity class P ?

a. No, because a PDA might not halt.

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

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

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

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

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

a. NP = All languages where we can guess membership quickly.

P = All languages where we can test membership quickly

b. NP = All languages where we can verify membership quickly.

P = All languages where we can guess membership quickly

c. NP = All languages where we can verify membership quickly.

P = All languages where we can test membership quickly

d. NP = All languages where we can verify membership quickly.

P = All languages where we cannot test membership quickly

c. NP = All languages where we can verify membership quickly.

P = All languages where we can test membership quickly

Which of the following boolean expressions are in 3-CNF?

a. (u ∨ y! ∨ z) ∧ (x ∨ v ∨ z) ∧ (x ∨ y! ∨ w!)

b. (x ∨ y! ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y! ∨ z!)

c. (u ^ y! ^ z) V (x ^ v ^ z) V (x ^ y! ^ w!)

d. (x ^ y! ^ z) V (x ^ y ^ z) V (x ^ y! ^ z!)

a. (u ∨ y! ∨ z) ∧ (x ∨ v ∨ z) ∧ (x ∨ y! ∨ w!)

b. (x ∨ y! ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y! ∨ z!)

Is SAT NP-complete?

a. Only if P=NP

b. This is unkown

c. Yes

d. No

c. Yes

Two models of computation are polynomially 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. cellular automata

b. random access machines (RAM)

c. multi-dimensional Turing Machines

d. multi-tape TMs

a,b,c,d: random access machines (RAM), multi-dimensional Turing Machines, multi-tape TMs, cellular automata

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. Newton's method

d. Zorn's lemma

b. Cantor's diagonal argument

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

a. 10011000

b. 01101001

c. 01100111

d. 10010110

a. 10011000

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

a. This is unknown

b. No

c. Yes

c. Yes

Is the following formula satisfiable? (x ∨ y) ∧ (x ∨ y!) ∧ (x! ∨ y) ∧ (x! ∨ y!)

a. Yes

b. No

b. No

Which of the following are true?

a. n^2 ∈ O(n)

b. 2n ∈ O(n)

c. n log n ∈ O(n^2)

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

b. 2n ∈ O(n)

c. n log n ∈ O(n^2)

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

Recall the pumping lemma for CFLs:

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

a. s1 = 0^p10^p1 ∈ F

b. s2 = 0^p 1^p 0^p 1^p ∈ F

c. s0 = 0^p1^p ∈ F

b. s2 = 0^p 1^p 0^p 1^p ∈ F

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

a) eK > 0En0 Vn > n0: |f(n) ≤ kg(n)

b) ek1 > 0ek2 > 0en0 > n0: k1g(n) ≤ f(n) k2g(n)

c) ek > 0en0 Vn > n0: f(n) ≥ kg(n)

d) Vk > 0en0 Vn > n0: |(fn)| < kg(n)

1. f(n) e 0(g(n)) (average case) ->

2. f(n) e O(g(n)) (worse case) ->

3. f(n) e o(g(n)) (loose upper bound) ->

4. f(n) e N(g(n)) (best case) ->

1. B

2. A

3. D

4. C

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

a. This in yet unknown.

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. 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

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

a. This is an open problem

b. True

c. False

b. True

What are T-decidable close under?

Choose all that apply

A) union

B) complement

C)kleenex

D)intersection

A) union

B) complement

C)kleenex

D)intersection

What are T-recognizable close under?

Choose all that apply

A) union

B) complement

C)kleenex

D)intersection

A) union

C)kleenex

D)intersection