Find the transitive closure of the following relation over the set {a,b,c,d}:

{(a,b), (a,c), (b,c)}

The four parts of a grammar are:

1. An alphabet N of grammar symbols called nonterminals.

2. An alphabet T of symbols called terminals. The terminals are distinct from the nonterminals.

3. A specific nonterminal S, called the start symbol.

4. A finite set of productions.

In the following grammar, which of the four parts of a grammar is b?

S → Λ | aB 

B → b | bB

The four parts of a grammar are:

1. An alphabet N of grammar symbols called nonterminals.

2. An alphabet T of symbols called terminals. The terminals are distinct from the nonterminals.

3. A specific nonterminal S, called the start symbol.

4. A finite set of productions.

In the following grammar, which of the four parts of a grammar is S?

S → Λ | aB 

B → b | bB

Which is a valid grammar for the following language:

{bb, bbbb, bbbbbb, …} = {(bb)ⁿ⁺¹ | n ∈ ℕ}

Which of the following statements are true about grammars? Select all that apply.

The four parts of a grammar are:

1. An alphabet N of grammar symbols called nonterminals.

2. An alphabet T of symbols called terminals. The terminals are distinct from the nonterminals.

3. A specific nonterminal S, called the start symbol.

4. A finite set of productions.

In the following grammar, which of the four parts of a grammar is B → b | bB?

S → Λ | aB 

B → b | bB

Which of the following is a valid inorder traversal of this binary tree?

Which of the following statements about recursive functions are true? Select all that apply.

Given the following definition for the nth Fibonnaci number:

fib(0) = 0,

fib(1) = 1,

fib(n) = fib(n - 1) + fib(n - 2) if n > 1.

Calculate fib(4).

What is the basis in the inductive definition of S?

S = {a, ab, abb, abbb, …}

Basis: ?

Induction: If x ∈ S, then xb ∈ S.