This problem is from Sipser's Theory of Computation 3rd Edition.

1.35 Prove that $A/B = \{\omega \ | \ \omega x \in A \ \mathrm{for\ some \ } x\in B\}$ is regular where $A$ is regular and $B$ is any language.

I want to verify that my proof is correct. It is as follows:

Let $A$ be a regular language. Then it has a DFA $N = (Q, \Sigma, \delta, q_0, F)$ such that $L(N) = A$. We will construct a DFA $M = (Q, \Sigma, \delta, q_0, F^{\prime})$ that recognizes $A/B$ and only $A/B$.
Let $P = \{p_1, \dots, p_k\} \subseteq Q$ be the set of states of $N$ that have a path to a final state of $N$. We will construct a DFA corresponding to each of these states.
Let $N_i = (Q, \Sigma, \delta, p_i, F)$ be the DFA identical to $N$ except the start state is $p_i \in P$. This means $L(N_i)$ contains strings $x$ where $\omega x \in A$ and $\delta^*(\omega, q_0) = p_i$. Now we determine $F^{\prime}$:

$F^{\prime} = \{p_i \in P : \exists x\in L(N_i) \cap B\}$

We will now prove that $L(M) = A/B$.

$(L(M) \subseteq A/B)$:
Let $\omega \in L(M)$. Then by construction we have: $$ \delta^*(q_0, \omega) = f^{\prime} \in F^{\prime} \\ \Rightarrow f^{\prime} = p_i \in P \ \ \mathrm{and} \ \ \exists x\in B\cap L(N_i) \ \ \mathrm{such \ that} \ \delta^*(p_i, x) = f \in F \\ \Rightarrow \delta^*(q_0, \omega x) = f \in F \\ \Rightarrow \omega x \in A \ \ (\mathrm{we \ also \ know \ } x \in B) \\ \Rightarrow \omega \in A/B $$

$(A/B \subseteq L(M))$:
Let $\omega \in A/B$. Then $\exists x \in B$ such that $\omega x \in A$. Let $\delta^*(q_0, \omega) = p_i$. ($p_i \in P$ is unique because $N$ is a DFA.) We know $\omega x \in A$ so $\delta^*(p_i, x) = f \in F$. Therefore $x \in L(N_i)$. We already know $x \in B$ so $x \in B \cap L(N_i)$. Hence $p_i \in F^{\prime}$. We conclude that $\omega \in L(M)$.

We have constructed a DFA that accepts $A/B$ and only $A/B$. Therefore $A/B$ is regular.

  • 1
    $\begingroup$ What are the final states in each of the copies of $N$? are they all the same final states? $\endgroup$ – nir shahar Apr 24 at 9:35
  • $\begingroup$ @nirshahar Yes, the same final states as $N$ itself. $\endgroup$ – Zara Apr 24 at 15:25
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Apr 24 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.