99年私立輔仁大學資工所離散數學線上測驗

1.

Given an alphabet Σ and a string w over Σ, the reversal of a string w is defined recursively as follows:

where ε denotes the empty string. If x and y are strings over Σ, use mathematical induction on the length of y to prove (xy)^R = y^Rx^R.

Let A = {1, 2, 3, 4, 5}

2.: If R is the equivalence relation on A that induces the partition , what is R = ?

Let A = {1, 2, 3, 4, 5}

3.: An equivalence relation on A is defined as: R = {(a, b) | a − b is the multiple of 2} Determine the partition of A induced by R.

4.: Let <A, o > be a group with identity e. If x o x = e for all x ∈ A, prove that <A, o > is an Abelian group.

5.: Solve the following recurrence relation.
a_n + na_n−1 = n!, n ≥ 1, a₀ = 1

6.

Convert the following nondeterministic finite state machine into deterministic form with 8 states only.

購買題庫後，可使用那些功能？