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

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