# Regular languages closed under quotients with arbitrary languages

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 \}$?

• What do you think? Have you tried proving or disproving it? – Yuval Filmus Dec 6 '15 at 22:18
• 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? – michbad Dec 6 '15 at 22:20
• No, there is no requirement of computability here. – Yuval Filmus Dec 6 '15 at 22:37

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$...