Midterm of Theory of Computation, 2022.

Name:

————————————

ID:

————————————

1. For all n ≥ 1, prove the following:

P(n) = 13 + 23 + 33 + ……..+ n3 = { n2 (n + 1)2 } / 4

Hints: Compute P(1), P(K), and then show that P(K+1) = P(K) + (K+1)3

2. Write the Formal Definition of the following DFA, including the Transition Table.

3. Create an NFA step-by-step for this Regular Expression:

(a U b U c) ⋅ (a U b U c)* ⋅ (a⋅b⋅c)

4. Consider the Following NFA.

a. Write down the Transition Table for the NFA.

b. Convert the NFA to DFA by presenting the DFA Transition Table.

c. Draw the DFA using minimal number states.

5. Solve the following two questions using Pumping Lemma:

a. Consider a language, L = {w.wR: w in {a, b}*}. Prove that L is not Regular.

Here, wR is the reverse of w. Please use the lemma with proper notation.

b. Consider that L = { xi yj zk | i, j, k >= 0 }. Is L Regular? Please use the lemma with proper notation.