Answer: True

Justification: By Definition 4.4, the right quotient is:

Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA recognizing $L_1$. We construct a DFA $M' = (Q, \Sigma, \delta, q_0, F')$ recognizing $L_1 / L_2$ by modifying the set of accepting states $F'$. For each state $q \in Q$, we determine if there exists a string $y \in L_2$ such that processing $y$ starting from state $q$ leads to an accepting state in $F$:

• Correctness: A string $x$ is accepted by $M'$ if and only if $\delta^*(q_0, x) = q \in F'$, which by definition of $F'$ means there exists $y \in L_2$ such that $\delta^*(q, y) = \delta^*(q_0, xy) \in F$. This is true if and only if $xy \in L_1$ for some $y \in L_2$, which is the exact definition of $L_1 / L_2$.
• Since $M'$ uses the exact same finite state set $Q$ and transition function $\delta$ as $M$, $M'$ is a valid DFA. Thus, $L_1 / L_2$ is regular. This closure property holds regardless of whether $L_2$ is regular, context-free, or completely undecidable.

Answer: False

Justification: We prove this by counterexample. Let the alphabet be $\Sigma = \{a, b\}$.

• Let $L_1 = \Sigma^*$, which is recognized by a simple 1-state DFA and is therefore regular.
• Let $L_2 = \{ a^n b^n \mid n \geq 0 \}$, which is a classic non-regular language.
• The union is: $$L_1 \cup L_2 = \Sigma^* \cup \{ a^n b^n \mid n \geq 0 \} = \Sigma^*$$ Since $\Sigma^*$ is regular, $L_1 \cup L_2$ is regular.
• Thus, $L_1$ and $L_1 \cup L_2$ are both regular, but $L_2$ is non-regular, disproving the claim.

Answer: True

Justification: The Pumping Lemma states:

By contrapositive, we use its negation to prove a language is non-regular:

However, the converse ($\text{Satisfies Pumping Lemma}(L) \implies \text{Regular}(L)$) does not hold. For example, consider the non-regular language $L = \{ a^i b^j c^k \mid \text{if } i=1 \text{ then } j=k \}$. Even though $L$ is non-regular, we can “pump” any string $s \in L$ that has a length $\geq p$ if we choose the pumping part $y$ from the $a^*$ prefix (provided $|s| \geq p$), meaning it satisfies the Pumping Lemma conditions. Thus, satisfying the lemma does not prove regularity.

Answer: True

Justification: Let $L_3 = (L_1 \cap \overline{L_2}) \cup (\overline{L_1} \cap L_2)$ be the symmetric difference of $L_1$ and $L_2$.

• If $L_1 = L_2$, then any string $w$ is either in both languages or in neither. Thus, $w$ cannot belong to $L_1 \cap \overline{L_2}$ (since $w \in L_1 \implies w \notin \overline{L_2}$) and cannot belong to $\overline{L_1} \cap L_2$. Hence, $L_3 = \emptyset$.
• If $L_1 \neq L_2$, there exists at least one string $x$ that is in one language but not the other, meaning $x \in L_3$, so $L_3 \neq \emptyset$.
• Since regular languages are closed under complement, intersection, and union, $L_3$ is regular. We can construct a DFA for $L_3$ and use the $ED_{DFA}$ decision algorithm (which checks for any reachable accepting state from the start state) to test if $L_3 = \emptyset$. This decides equality.

Correct Options: B, C

Justification:

• A is incorrect: Let $L_1 = \emptyset$ (regular) and $L_2 = \{ a^n b^n \mid n \geq 0 \}$ (non-regular). Their intersection is $L_1 \cap L_2 = \emptyset$, which is regular.
• B is correct: Suppose for contradiction that $L_2 - L_1 = R$ is regular. We can express $L_2$ as: $$L_2 = R \cup (L_2 \cap L_1)$$ Since $L_1$ is finite, any subset of $L_1$ (such as $L_2 \cap L_1$) must also be finite. Since all finite languages are regular, $L_2 \cap L_1$ is regular. Since regular languages are closed under union, $R \cup (L_2 \cap L_1) = L_2$ must be regular, which directly contradicts our premise that $L_2$ is non-regular.
• C is correct: By definition, $L_1 \cap L_2 \subseteq L_1$. Since $L_1$ is finite, any subset of $L_1$ must also be finite. Since all finite languages are regular, $L_1 \cap L_2$ is guaranteed to be regular.
• D is incorrect: Let $L_1 = \emptyset$ (regular) and $L_2 = \{ a^n b^n \mid n \geq 0 \}$ (non-regular). Their concatenation is $L_1 \cdot L_2 = \emptyset$, which is regular.

Correct Options: A, C

Justification:

• A is correct: Regular languages are closed under homomorphism (Theorem 4.3). If we have a regular expression $R$ for $L$, we get a regular expression for $h(L)$ by applying $h$ to each alphabet symbol in $R$.
• B is incorrect: Let $\Sigma = \{a, b\}$ and $\Gamma = \{c\}$. Define $h$ by $h(a) = \varepsilon$ and $h(b) = \varepsilon$. Let $L = \{ a^n b^n \mid n \geq 0 \}$ (non-regular). Then $h(L) = \{\varepsilon\}$, which is finite and therefore regular. Thus, $h(L)$ is regular but $L$ is non-regular.
• C is correct: Regular languages are closed under inverse homomorphism. If $M' = (Q, \Gamma, \delta', q_0, F')$ is a DFA for $L'$, we construct a DFA $M = (Q, \Sigma, \delta, q_0, F')$ for $h^{-1}(L')$ where the transition function is defined as $\delta(q, a) = \delta'^*(q, h(a))$. Since $M$ has the same finite state set $Q$, $h^{-1}(L')$ is regular.
• D is incorrect: Let $\Sigma = \{a\}$ and $\Gamma = \{b\}$. Define $h$ by $h(a) = \varepsilon$. Let $L' = \{ b^n \mid n \text{ is a perfect square} \}$ (non-regular). Since $h(a) = \varepsilon$, for any $w \in \Sigma^*$, $h(w) = \varepsilon$. Since $\varepsilon = b^0 \in L'$ (as 0 is a perfect square), $h(w) \in L'$ is true for all $w \in \Sigma^*$. Thus, $h^{-1}(L') = \Sigma^*$, which is regular, but $L'$ is non-regular.

Part 1: Product DFA Construction

We define $M = (Q, \Sigma, \delta, q_0, F)$ where:

• $Q = Q_1 \times Q_2 = \{ (r_1, r_2) \mid r_1 \in Q_1 \text{ and } r_2 \in Q_2 \}$
• $q_0 = (q_1, q_2)$
• $F = F_1 \times F_2 = \{ (r_1, r_2) \mid r_1 \in F_1 \text{ and } r_2 \in F_2 \}$
• For each $(r_1, r_2) \in Q$ and $a \in \Sigma$: $$\delta((r_1, r_2), a) = (\delta_1(r_1, a), \delta_2(r_2, a))$$

Part 2: Inductive Proof

We prove the claim $\delta^*(q_0, w) = (\delta_1^*(q_1, w), \delta_2^*(q_2, w))$ by induction on $n = |w|$.

• Base Case ($n = 0$): Let $w = \varepsilon$. By definition of the extended transition function $\delta^*$:

  $$\delta^*(q_0, \varepsilon) = q_0 = (q_1, q_2)$$

  Independently, for $M_1$ and $M_2$:

  $$(\delta_1^*(q_1, \varepsilon), \delta_2^*(q_2, \varepsilon)) = (q_1, q_2)$$

  The base case holds.

• Inductive Hypothesis: Assume that for any string $v \in \Sigma^*$ of length $|v| = k \geq 0$, the transition holds:

  $$\delta^*(q_0, v) = (\delta_1^*(q_1, v), \delta_2^*(q_2, v))$$

• Inductive Step ($n = k + 1$): Let $w = va$ where $|v| = k$ and $a \in \Sigma$. Applying the recursive definition of $\delta^*$:

  $$\delta^*(q_0, va) = \delta(\delta^*(q_0, v), a)$$

  Applying the Inductive Hypothesis to substitute $\delta^*(q_0, v)$:

  $$\delta^*(q_0, va) = \delta((\delta_1^*(q_1, v), \delta_2^*(q_2, v)), a)$$

  By our definition of the product transition function $\delta$:

  $$\delta((\delta_1^*(q_1, v), \delta_2^*(q_2, v)), a) = (\delta_1(\delta_1^*(q_1, v), a), \delta_2(\delta_2^*(q_2, v), a))$$

  Using the recursive definition of $\delta_1^*$ and $\delta_2^*$:

  $$(\delta_1(\delta_1^*(q_1, v), a), \delta_2(\delta_2^*(q_2, v), a)) = (\delta_1^*(q_1, va), \delta_2^*(q_2, va))$$

  Therefore, $\delta^*(q_0, w) = (\delta_1^*(q_1, w), \delta_2^*(q_2, w))$ holds for $|w| = k + 1$. By induction, this is true for all strings $w \in \Sigma^*$. $\blacksquare$

Part 3: Acceptance Guarantee

A string $w$ is accepted by $M$ if and only if:

By substituting our proven identity and the definition of $F$:

This is true if and only if $w \in L_1$ and $w \in L_2$, meaning $w \in L_1 \cap L_2$. Thus, $L(M) = L_1 \cap L_2$.

Step 1: DFA for $L_1$

$L_1$ consists of all strings containing at least one $b$.

• States $Q$: $\{q_0, q_1\}$ where $q_0$ is the start state (no $b$ read yet) and $q_1$ is the accept state (at least one $b$ read).
• Transitions:
  • $\delta(q_0, a) = q_0$, $\delta(q_0, b) = q_1$
  • $\delta(q_1, a) = q_1$, $\delta(q_1, b) = q_1$
• Accepting States $F_1$: $\{q_1\}$

Step 2: Applying Right Quotient State-Filtering

We must find for each state $q \in \{q_0, q_1\}$ if there exists some string $y \in L_2 = L(b(a \cup b)^*b)$ such that $\delta^*(q, y) \in F_1 = \{q_1\}$.

1. Test State $q_1$:
   • Let $y = bb \in L_2$.
   • $\delta^*(q_1, bb) = q_1 \in F_1$.
   • Since a valid $y$ exists, $q_1 \in F'$.
2. Test State $q_0$:
   • Any string $y \in L_2$ must start with the character $b$.
   • Processing the first symbol $b$ of $y$ from $q_0$ moves the machine to state $q_1$: $$\delta(q_0, b) = q_1$$
   • Since $q_1$ is a trap-accepting state (all subsequent transitions stay in $q_1$), processing the remainder of the string $y$ will keep the machine in $q_1$: $$\delta^*(q_0, y) = q_1 \in F_1$$
   • Since a valid $y$ exists (e.g., $bb \in L_2$), $q_0 \in F'$.

Thus, the new accepting state set is:

Step 3: Regular Expression for $L_1 / L_2$

Since both states of our DFA are now accepting ($F' = \{q_0, q_1\}$), the modified machine accepts all strings in $\Sigma^*$. Therefore:

Intuitive Verification: For any string $x \in \Sigma^*$, we can append $y = bb \in L_2$ to form $w = xbb$. Since $w$ contains at least one $b$, $w \in L_1$. Since $xbb \in L_1$ and $bb \in L_2$, $x$ belongs to the quotient $L_1 / L_2$.

Part 1: Non-regularity Proof for $L_a$

Suppose for contradiction that $L_a$ is regular. Let $p$ be the pumping length.

• We choose the string: $$s = a^p b^p c^{2p}$$ Since $s \in L_a$ (with $n=p, k=p$) and $|s| = 4p \geq p$, the Pumping Lemma guarantees that $s$ can be split into $s = xyz$ satisfying:
  1. $|xy| \leq p$
  2. $|y| \geq 1$
  3. $xy^iz \in L_a$ for all $i \geq 0$.
• Analyze the constraint $|xy| \leq p$: Since the first $p$ symbols of $s$ are entirely $a$’s, the substring $xy$ must consist entirely of $a$’s. Therefore, the pumpable string $y$ must be of the form: $$y = a^m \quad \text{for some } m \geq 1$$
• Pumping down ($i = 0$): The pumped string is: $$s' = xy^0z = xz = a^{p-m} b^p c^{2p}$$ For $s'$ to belong to $L_a$, the number of $c$’s must equal the sum of the number of $a$’s and $b$’s: $$\text{Count}(c) = \text{Count}(a) + \text{Count}(b) \implies 2p = (p-m) + p \implies 2p = 2p - m \implies m = 0$$ This contradicts the requirement that $|y| \geq 1$ ($m \geq 1$). Thus, $L_a$ is not regular. $\blacksquare$

Part 2: Non-regularity Proof for $L_b$

Suppose for contradiction that $L_b = \{ w \in \{a,b\}^* \mid n_a(w) \neq n_b(w) \}$ is regular. Let $p$ be the pumping length.

• Let $p!$ be the factorial of $p$ (which is divisible by all integers from 1 to $p$). We choose the string: $$s = a^p b^{p + p!}$$ Since $p \neq p + p!$ (as $p! \geq 1$), $s \in L_b$. Since $|s| = 2p + p! \geq p$, $s$ can be split into $s = xyz$ with $|xy| \leq p$ and $|y| \geq 1$.
• Since $|xy| \leq p$, the substring $y$ consists entirely of $a$’s: $$y = a^k \quad \text{for some } 1 \leq k \leq p$$
• We choose to pump the string to step $i + 1$ where $i = \frac{p!}{k}$. Since $1 \leq k \leq p$, $k$ divides $p!$, so $i$ is a valid integer.
• Let’s evaluate the pumped string $s'$ for this choice of $i$: $$s' = xy^{i+1}z$$ The number of $a$’s in $s'$ is: $$\text{Count}(a) = p + i \cdot k = p + \left(\frac{p!}{k}\right) \cdot k = p + p!$$ The number of $b$’s remains unchanged: $$\text{Count}(b) = p + p!$$ Since $\text{Count}(a) = \text{Count}(b)$, the string $s'$ has an equal number of $a$’s and $b$’s. Thus, $s' \notin L_b$. This contradiction proves that $L_b$ is not regular. $\blacksquare$

Step 1: Formulate Symmetric Difference State-Set

The product DFA states are $Q = Q_1 \times Q_2$.

• Start state: $q_0 = (A, C)$
• Symmetric difference accepting states are defined as: $$F_{diff} = (F_1 \times (Q_2 - F_2)) \cup ((Q_1 - F_1) \times F_2)$$
  • $F_1 = \{B\}$, so $Q_1 - F_1 = \{A\}$
  • $F_2 = \{D, E\}$, so $Q_2 - F_2 = \{C\}$ $$F_{diff} = (\{B\} \times \{C\}) \cup (\{A\} \times \{D, E\}) = \{(B, C), (A, D), (A, E)\}$$

Step 2: Compute Reachable Transitions

We trace transitions starting from $q_0 = (A, C)$:

1. From State $(A, C)$:
   • On $a$: $(\delta_1(A, a), \delta_2(C, a)) = (B, D)$
   • On $b$: $(\delta_1(A, b), \delta_2(C, b)) = (A, C)$ (Self-loop)
2. From State $(B, D)$:
   • On $a$: $(\delta_1(B, a), \delta_2(D, a)) = (B, E)$
   • On $b$: $(\delta_1(B, b), \delta_2(D, b)) = (A, C)$
3. From State $(B, E)$:
   • On $a$: $(\delta_1(B, a), \delta_2(E, a)) = (B, E)$ (Self-loop)
   • On $b$: $(\delta_1(B, b), \delta_2(E, b)) = (A, C)$

Let’s check if any other states in $Q$ are reachable. The only reachable states are:

Step 3: Emptiness Decision Algorithm

We apply the marking algorithm of Theorem 4.4 to check if any accepting state in $F_{diff}$ is reachable from our start state $q_0 = (A, C)$:

• Iteration 1: Mark the start state: $$\text{Marked} = \{(A, C)\}$$
• Iteration 2: Mark states with incoming transitions from marked states: $$\text{From } (A, C) \text{ on } a \to \text{Mark } (B, D)$$ $$\text{Marked} = \{(A, C), (B, D)\}$$
• Iteration 3: Repeat the process: $$\text{From } (B, D) \text{ on } a \to \text{Mark } (B, E)$$ $$\text{Marked} = \{(A, C), (B, D), (B, E)\}$$
• No more new states can be marked. The algorithm halts.

Now we compare our marked set with $F_{diff} = \{(B, C), (A, D), (A, E)\}$:

Since no accepting states are marked, the symmetric difference language is empty. Therefore, we decide that:

Intuitive Verification: Both machines accept any string containing at least one $a$. $M_1$ transitions to state $B$ on the first $a$ and stays in $B$ (or returns to $A$ only on $b$). Actually, let’s verify if $M_1$ accepts strings ending in $a$. Yes, any string ending in $a$ lands in $B$. Any string ending in $b$ lands in $A$. For $M_2$: reading $a$ moves $C \to D \to E$. Reading $b$ always resets to $C$. Thus, any string ending in $a$ lands in $D$ or $E$ (accepting), and any string ending in $b$ resets to $C$ (non-accepting). Both DFAs recognize the exact same regular language $L = \{ w \in \{a,b\}^* \mid w \text{ ends with the character } a \}$, proving equivalence!