[Solved]: Closure against right quotient with a fixed language

Problem Detail: 

I'd really love your help with the following:

For any fixed $L_2$ I need to decide whether there is closure under the following operators:

1. $A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$

2. $A_l(L)=\{x \mid \exists y \in L : xy \in L_2\}$.

The relevant options are:

1. Regular languages are closed under $A_l$ resp. $A_r$, for any language $L_2$

2. For some languages $L_2$, regular languages are closed under $A_l$ resp. $A_r$, and for some languages $L_2$, regular languages are not closed under $A_l$ resp. $A_r$.

I believed that the answer for (1) should be (2), because when I get a word in $w \in L$ and $w=xy$ I can build an automaton that can guess where $x$ turning to $y$, but then it needs to verify that $y$ belongs to $L_2$ and if it won't be regular, how would it do that?
The answer for that is (1).

What should I do in order to analyze those operators correctly and to determine if the regular languages are closed under them or not?

Asked By : Jozef

Answered By : Ran G.

To answer these question, we need allow any $L_2$. So let's think that $L_2$ is a very complex language (say, some undecidable language.)

---

Lets start from the easy question: $A_l(L)$ (question part 2). Take $L_2$ to be undecidable, and $L=\{\varepsilon\}$. What happens?

(moral: Always check the "extremes": empty $L$, $L=\{\varepsilon\}$ and $L=\Sigma^*$...)

---

Now for $A_r$. This is a great question (usually bonus question in Final/Homeworks). Indeed, regular languages are closed under $A_r$ for any language $L_2$. Even undecidable $L_2$. Cool, right?

So how can we build an automaton for $A_r(L)$ if there is no machine that accepts $L_2$?

Here comes the magic of "abstract thinking",i.e., existential proof. If someone gives us $L_2$ we can use this information to show that there exists some automaton to solve $A(L)$. Now the details.

We start from the automaton of $L$ (call is $DFA_L$). Assume that after processing $x$ we end up in a state $q$. We need to accept if there exists $y\in L_2$ such that if we continue from $q$ processing $y$ we will end up in a final state of $DFA_L$. There is no machine that can tell us if $y$ is in $L_2$, but we can make $q$ a final state of $DFA_{A_L}$ if the above condition holds, i.e., if there exists some $y\in L_2$ such that if we start at $q$ and process $y$ we end up in a final state of $DFA_L$.

so to build $DFA_{A_L}$ we examine each one of the states of $DFA_L$ and make each state $q$ an accepting state if we can take some $y\in L_2$ and this $y$ will lead us from $q$ to an accepting state of $DFA_L$.

So ok, $L_2$ is infinite, and we might have no computer to list all the words in $L_2$, but all of this doesn't matter... the above automaton is well-defined, even if I can't draw it to you state by state. Magic.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1547