1/60
Looks like no tags are added yet.
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|
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
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
a. Regular expression
Match the recognizer with the generator:
DFA
a. Regular expression
b. Context free grammar
a. Regular expression
Match the recognizer with the generator:
NFA
a. Regular expression
b. Context free grammar
b. Context free grammar
Match the recognizer with the generator:
PDA
a. Regular expression
b. Context free grammar
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
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
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
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
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
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)
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)
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)
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)
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
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.
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)
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
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
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 = {
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.
a. True
Decidability of languages does not depend on the model of computation.
a. True
b. False
c. This is an open problem
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.
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
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
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
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)
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
????
???
False
Context free languages are closed under intersection
a. True
b. False
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
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
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
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
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
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)
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
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).
d. True
Regular languages are closed under union and intersection
a. This is unknown
b. False
c. This depends on the language
d. True
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)*
a. No
All languages are regular.
a. No
b. Yes
c. This is still an open problem
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.
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.
b. No
Are all context free languages regular?
a. Yes
b. No
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
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}*
b. Adfa = {
c. Anfa = {
d. EQdfa = {
Which of the following languages are decidable?
a. Aim = {
b. Adfa = {
c. Anfa = {
d. EQdfa = {
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.
c. True
Decidability of languages does not depend on the model of computation.
a. This is an open question
b. False
c. True
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.
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.
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.
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
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
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.
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.
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)
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
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.
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)