Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Theory of Computation

Mock Test

Part I: Models of Computation

Question 1

Which of the following DFAs recognise the same language?

(A)  a and b

(B) b and c

(C)  a and c

(D)  all of them recognise the same language

(E)  each one recognises a different language

Question 2

Given two DFAs A and B with p and q states, respectively, what can you say about the number of states of a minimal DFA that recognises the union of the languages recognised by A and B? This number is

(A) precisely p + q + 1.

(B)  at least p + q + 1.

(C)  at most pq.

(D)  none of the above.

Question 3

Construct a DFA over a binary alphabet, {0, 1}, that accepts the words with even number of zeros.  What ω-language does it recognise,  i.e.  if the input is infinite?

(A)  All words that contain infinitely many zeros.

(B)  All words that contain finitely many and even number of zeros.

(C)  All words that satisfy either of the two properties above.

(D)  None of the above.

Question 4

Which of the following strings belong to the regular language (a* ba)* ?

(A)  baabab

(B)  aabbba

(C)  aaabab

(D)  aababa

Question 5

Consider the following two LTL expressions:  口♢p and ♢口p.  Which of them logically implies the other?

(A)  The former implies the latter.

(B)  The latter implies the former.

(C)  Each one implies the other, i.e. they are equivalent.

(D)  Neither of them implies the other.

Part II: Algorithms and Complexity

Question 6

Let f(n) and g(n) be two positive functions defined on the natural numbers. Suppose there exist constants c > 0 and n0  such that f(n0 ) ≤  cg(n0 ).  Which statement below can we deduce from this?

(A)  f(n) = O(g(n))

(B)  f(n) = Ω(g(n))

(C)  f(n) = Θ(g(n))

(D)  Each of the above can be deduced.

(E)  None of the above can be deduced.

Question 7

Let T(n) = 8T( n/2 ) + n 2 (where we interpret n/2 to mean ⌊ n/2 ⌋). Which statement below is true?

(A) T(n) = Θ(n2 ).

(B) T(n) = Θ(n3 ).

(C) T(n) = Θ(n3 lgn).

(D) T(n) = Θ(n4 ).

(E)  None of the above is true.

Question 8

Let A be a 3 × 3 matrix.  Let B be a 3 × 1 matrix.  Let C be a 3 × 3 matrix. Which statement below is true?

(A)  The number of ways to parenthesize ABC is 27.

(B)  The number of ways to parenthesize ABC is 28.

(C)  The number of ways to parenthesize ABC is 1.

(D) It is not possible to compute the matrix product ABC.

(E)  None of the above.

Question 9

Which problem below can be solved by a greedy algorithm?

(A)  Longest Common Subsequence.

(B)  0-1 knapsack.

(C)  Fractional knapsack.

(D)  Rod cutting.

(E)  None of the above.

Question 10

For r ≥ 17, let H be a star graph with r + 1 vertices, where vertex u is the center of the star and vertices v1 , v2 ,..., vr  are its leafs.  That is, H has the edges uv1 , uv2 ,..., uvr . Now, let G be the graph which is obtained from H by adding a new vertex z and the edge zv1 . Which statement below is true?

(A)  G is a bipartite graph but not a cograph.

(B)  G is a cograph but not a bipartite graph.

(C)  G is both a bipartite graph and a cograph.

(D)  G is neither a bipartite graph nor a cograph.