1
$\begingroup$

When proving that that the quotient of a regular language $R$ and an arbitrary language $B$, I understand you take a DFA $M$ accepting $R$, and then construct a DFA that is the same, but its final states are those from which we can reach a final state of $M$ with a string from $B$. How can we just say it's possible to take such a set?

Does this proof also work for a similar property (I don't know the name) that creates the set $\{ x \mid \forall y \in B : xy \in R \} $?

$\endgroup$
  • 2
    $\begingroup$ What do you think? Have you tried proving or disproving it? $\endgroup$ – Yuval Filmus Dec 6 '15 at 22:18
  • $\begingroup$ It's the question of constructing such sets of states from which we reach a final state by some/all strings of B. Would we need to prove they are decidable? $\endgroup$ – michbad Dec 6 '15 at 22:20
  • 1
    $\begingroup$ No, there is no requirement of computability here. $\endgroup$ – Yuval Filmus Dec 6 '15 at 22:37
4
$\begingroup$

The (right) quotient of $R$ by $B$ is the language $$ RB^{-1} = \{x \in A^* \mid \exists y \in B,\ xy \in R\} $$ and indeed, if $(Q, A, \cdot, q_0, F)$ is the minimal DFA of $R$, then $RB^{-1}$ is accepted by the automaton $(Q, A, \cdot, q_0, S)$, where $$ S = \{q \in Q \mid \exists y \in B\ \ q \cdot y \in F\}. $$ On the other hand, let $R/B = \{x \in A^* \mid \forall y \in B\ \ xy \in R\}$. Then one gets $$ R/B = \bigcap_{y \in B} \{ x \in A^* \mid xy \in R \} = \bigcap_{y \in B} Ry^{-1} $$ Since $R$ is regular, there are only finitely many distinct languages of the form $Ry^{-1}$, and each of it is regular. It follows that $R/B$ is also regular.

This gives a proof that the languages $RB^{-1}$ and $R/B$ are regular for any $B$. However, if you want to find effectively an automaton accepting these languages, this is a different story and you may need to identify which of the right quotients $Ru^{-1}$ are of the form $Ry^{-1}$ with $y \in B$, a question that might be undecidable, depending on $B$ and $R$...

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.