Let's break down the problem and solve it step-by-step as instructed. --- # **Step 1: Regular Expressions and DFA Construction** ## **Given:** - Alphabet: \(\Sigma = \{a, b\}\) - Regular Expression \(E = (a + b)^* bb (a + b)^*\) --- ## **A. Make a DFA \(M\) such that \(L(M) = L(E)\)** ### **Language Description:** - \(L(E)\) represents all strings over \(\{a, b\}\) that contain "bb" as a substring. ### **DFA Construction:** Let's construct a minimal DFA for strings containing "bb": #### **States:** - \(q_0\): Start state, no 'b' seen yet. - \(q_1\): 'b' seen, but not "bb". - \(q_2\): "bb" seen (accepting state). #### **Transitions:** - From \(q_0\): - On 'a', stay at \(q_0\). - On 'b', go to \(q_1\). - From \(q_1\): - On 'a', go back to \(q_0\). - On 'b', go to \(q_2\). - From \(q_2\) (once "bb" has been seen, always accept): - On 'a' or 'b', stay at \(q_2\). #### **DFA Table:** | State | a | b | |-------|-----|-----| | q0 | q0 | q1 | | q1 | q0 | q2 | | q2 | q2 | q2 | - Start State: \(q_0\) - Accepting State: \(q_2\) --- ## **B. DFA \(M'\) for the Complement** We want \(L(M') = \overline{L(E)}\): strings **not** containing "bb". - Complement the accepting/non-accepting states of \(M\): | State | a | b | Accepting? | |-------|-----|-----|------------| | q0 | q0 | q1 | Yes | | q1 | q0 | q2 | Yes | | q2 | q2 | q2 | **No** | - Now, \(q_0\) and \(q_1\) are accepting; \(q_2\) is not. --- ## **C. Regular Expression \(E'\) for \(L(M')\)** We need a regular expression for all strings over \(\{a, b\}\) that **do not contain "bb"** as a substring. ### **Let’s use Arden’s Lemma and substitution:** Let: - \(R_0\): Strings to reach \(q_0\) - \(R_1\): Strings to reach \(q_1\) - \(R_2\): Strings to reach \(q_2\) (which we want to avoid—so focus on \(R_0\) and \(R_1\)) #### **Equations:** - \(R_0 = a R_0 + a R_1 + \epsilon\) (from \(q_0\), on 'a' stay at \(q_0\); on 'b' go to \(q_1\)) - \(R_1 = b R_0\) (from \(q_1\), on 'a' back to \(q_0\); on 'b' to \(q_2\), but we do **not** want to reach \(q_2\)) But let's use a known result: **A string with no "bb" as substring** can be described as: - Each 'b' is not immediately followed by another 'b'. - So: \( (a^* (b a^*)^*) \) **Explanation:** - Arbitrary many 'a's. - Followed by zero or more occurrences of a 'b' followed by zero or more 'a's. ### **Therefore:** \[ E' = a^* (b a^*)^* \] --- # **Step 2: Algorithm for DFA DifferInfinite** ## **Problem Restatement:** - **Input:** DFAs \(M\) and \(N\) - **Question:** Do \(M\) and \(N\) differ on infinitely many inputs? ## **Algorithm Steps:** ### **1. Construct DFA for Symmetric Difference** - Construct DFA \(D\) such that \(L(D) = L(M) \Delta L(N) = (L(M) \setminus L(N)) \cup (L(N) \setminus L(M))\). - This can be done by taking the **cross product** of \(M\) and \(N\). ### **2. Check if \(L(D)\) is infinite** - Use the **DFA Infiniteness** algorithm (from class). - The language of a DFA is infinite **iff** there is a cycle reachable from the start state that leads to an accepting state. ### **3. Output** - If \(L(D)\) is infinite, output "Yes" (they differ on infinitely many strings). - Otherwise, output "No". --- ## **Pseudocode** ```text Input: DFAs M and N 1. Construct DFA D for the symmetric difference L(M) Δ L(N) - For each state (m, n) in M x N - Accepting if (m is accepting and n is not) or (m is not and n is) 2. Run DFA-Infinite(D) - If infinite, output "Yes" - Else, output "No" ``` --- # **Summary of Answers** ## **1.** - **A:** DFA for \( (a + b)^* bb (a + b)^* \) constructed above. - **B:** Complement DFA constructed. - **C:** Regular expression for complement: \( \boxed{a^*(b a^*)^*} \) ## **2.** - **Algorithm:** Construct symmetric difference DFA, check for infiniteness. --- ## **If you need the explicit state diagrams, let me know!**