Question Bank

To prove a goal $G$ when a disjunction $A ∨ B$ is known:

Let $P, Q, R$ be propositional variables. Which of the following propositional formulas correspond to the boolean function with 3 arguments that returns $\mathbb{T}$ when its inputs represent the binary encoding of a prime number:

Consider the clause set $$\{\{¬P, ¬Q, R\}, \{P, ¬Q, ¬R\}, \{¬P, R\}, \{P, ¬Q, R\}, \{¬Q, ¬R\}\}$$ . The first step in running the Davis Putnam method is:

Let $Σ = \{a, b, c\}$, $G = ({S, A, B}, Σ, \{S → AAb, A → aA | B, B → ϵ | cB\}, S)$, and $G_1$ be the grammar equivalent with G but without ϵ-productions. Which of the following assertions are correct?

Consider the set of all strings of balanced parentheses of two types: round and square. An example of where these strings come from is as follows. If we take expressions in C, which use round parentheses for grouping and for arguments of function calls, and use square brackets for array indexes, and drop out everything but the parentheses, we get all strings of balanced parentheses of these two types. For example, $$f(a[i] ∗ (b[i][j], c[g(x)]), d[i])$$ becomes the balanced parentheses string $$([]([][][()])[])$$. A grammar $G = \{V_N, V_T , S, P\}$ for generating the strings of round and squared parentheses that are balanced is:

Let $V = \{S, X, Y, Y1, Y2\}, Σ = \{a, b, c\}$ and the grammar $G = (V, Σ, P, S)$ with $$P = \{S → X | Y, X → aX | b, Y → Z | aY b, Z → c^2Zb | ϵ\}$$. What is the language generated by G?

Which of the following strings are accepted by the DFA with the transition diagram:

Let $Σ = \{a, b, c\}$ and L be the complement of the language $\{a^mbc^n | m ≥ n\}: L = Σ^∗ − \{a^mbc^n | m ≥ n\}$. Is L a regular language?

Let $Σ = \{a, b, c, d\}, Γ = Σ∪\{⊥\}$, and the NPDA $M = (\{q0, q1, q2, q3, q4\},Σ, Γ, δ, q0,⊥, {q4})$ with transition diagram:

Which of the following strings match the regular expression $a^∗bb(ab|ba)^∗$

Let L be the language generated by the grammar $G = (V_N, V_T , S, P)$ where
$V_N = \{S, A, B, C, X, Y, Z\}$,
$V_T = \{a, b, c\}$, and
$P = \{ S → ϵ | AX | BY | CZ, X → ϵ | BY | CZ, Y → ϵ | AX | CZ, Z → ϵ | AX | BY, A → a, B → b, C → c\}$.
Is L a regular language?

Let L be the language generated by the grammar $G = (V_N, V_T , S, P)$ where
$V_N = \{S, A, B, C, X, Y, Z\}$,
$V_T = \{a, b, c\}$, and
$P = \{ S → ϵ | AX | BY | CZ, X → ϵ | BY | CZ, Y → ϵ | AX | CZ, Z → ϵ | AX | BY, A → a, B → b, C → c\}$. How many strings of length 4 does L contain?

Let L be the language generated by the grammar
$G = (V_N, V_T , S, P)$ where
$V_N = \{S, A, B, C, X, Y, Z\}, V_T = \{a, b, c\}$, and
$P = \{ S → ϵ | AX | BY | CZ, X → ϵ | BY | CZ, Y → ϵ | AX | CZ, Z → ϵ | AX | BY, A → a, B → b, C → c\}$.
Which of the following statements is true?

(This question is also wrong)

Let L be the language generated by the grammar $G = (V_N, V_T , S, P)$ where
$V_N = \{S, A, B, C, X, Y, Z\}$,
$V_T = \{a, b, c\}$, and
$P = \{ S → ϵ | AX | BY | CZ, X → ϵ | BY | CZ, Y → ϵ | AX | CZ, Z → ϵ | AX | BY, A → a, B → b, C → c\}$.
Let $s_n$ be the number of strings from $L$ with length $n$. For every n > 1, the following recursive relation holds:

A message is a sequence of two types of signals: of type A which last for 1 second and of type B which last for 2 seconds. E.g., the message $ABAAB$ lasts 7 seconds. How many different messages last 10 seconds?

In how many ways can be colored the following configuration by using 2 colors: red and black?

Which of the following recurrence relations hold for any $n > k > 0$?

Which is the minimum weight spanning tree of the following connected graph? (hint: apply the
Kruskal algorithm)

Which is the Prüfer sequence of the following tree?