Closure against right quotient with a fixed language

Question

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?

Answer 1

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.

Answer 2

I'm not sure if you are looking for an answer to the problem or not, so I don't provide it directly. (I can if you want it, though.)

You asked:

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

Your starting approach is a good one. As with all "open" theory questions, you should get an intuitive feel for whether it is true or not. Usually this is by trying examples (both common and edge-case) or investigating special cases (e.g. what if $L_2$ is regular? context-free?). For this problem, you need to develop some guess as to whether you can build an automaton/regex for the operators or not. After that:

• If you think that you can, you need to be able to construct this automaton/regex for any regular input language $L$.
• If you think that you cannot, you would typically find example languages $L$ and $L_2$ such that $A_x$ is not closed.

(and if one approach isn't working, you can always try the other.)

---

For the problem itself:

These both are the right quotient operator. (I believe left quotient involves leaving the postfix instead of the prefix.) The difference between the two is that $A_l(L) = L_2 / L$ while $A_r(L) = L / L_2$, where $L_2$ is fixed in both cases.

You have some intuition about $A_r$, so here's something to think about for $A_l$: $A_l$ gives a modified version of $L_2$. Since $L_2$ could be nonregular, is it possible for $A_l$ to leave $L_2$ unchanged? If so, then $A_l$ is not regular in that case. Otherwise, we will have to argue that $A_l$ makes $L_2$ regular in all cases.