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.
For this short paper activity, you will learn about the three delays model, which explains…
Topic : Hospital adult medical surgical collaboration area a. Current Menu Analysis (5 points/5%) Analyze…
As a sales manager, you will use statistical methods to support actionable business decisions for Pastas R Us,…
Read the business intelligence articles: Getting to Know the World of Business Intelligence Business intelligence…
The behaviors of a population can put it at risk for specific health conditions. Studies…