2
$\begingroup$

This question already has an answer here:

Let $L_1$ and $L_2$ be two languages over an alphabet $\Sigma$. The quotient of $L_1$ and $L_2$ is the language $L_1/L_2 = \{x : \exists y \in L_2, xy \in L_1\}$

Show that if $L_1$ is regular and $L_2$ is any language, then $L_1/L_2$ is regular.

I've looked up online how to do this but it not very helpful. So far I know that $L_1$ and $L_2 \in \Sigma^*$ and that $L_1 = \{xy \mid x \in \Sigma^* \text{ and } y \in \Sigma^*\}$ and we can say it is regular by concatenation and $L_2 \in \Sigma^*$ which is any language.

From here, we can say that in $L_1$, $x$ has an accept state before going to the DFA for $y$ and $L_1 / L_2$ would just be eliminating the DFA for $y$, leaving you with just $x$, which still has an accept state, which makes it regular. I don't know how to put this in words and not pictures.

$\endgroup$

marked as duplicate by Ran G., David Richerby, Rick Decker, Juho, Luke Mathieson May 2 '16 at 8:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Your proof outline seems to assume that $L_2$ is regular. $\endgroup$ – Yuval Filmus Apr 6 '16 at 18:21
1
$\begingroup$

Let $A$ be a DFA accepting $L_1$, and let $Q$ be its set of states. Denote by $L_A(q)$ the set of words which cause $A$ to move from its initial state to state $q$. For each state $q$ and word $w$, one of the following holds (exercise):

  1. For every $x \in L_A(q)$, $xw \in L_1$.
  2. For every $x \in L_A(q)$, $xw \notin L_1$.

We now modify $A$ by determining its accepting states as follows. A state $q$ is accepting if for some word $w \in L_2$, $xw \in L_1$ for all $x \in L_A(q)$. It is not too hard to show that the modified automaton accepts $L_1/L_2$ (exercise).

$\endgroup$
  • $\begingroup$ I'm sorry i don't follow. $\endgroup$ – Darkflame Apr 6 '16 at 19:10
  • $\begingroup$ You'll have to wait for another answer. Or ask your TA for help. $\endgroup$ – Yuval Filmus Apr 6 '16 at 19:11
  • $\begingroup$ I've been looking at this over and over so i was wondering if this was the concept : "assume that L1 is regular such that there is a DFA that recognizes L1" or are you trying to say there is a regular language A which accepts L1 which makes it regular? $\endgroup$ – Darkflame Apr 6 '16 at 20:16
  • $\begingroup$ In my book, by definition a language is regular iff some DFA accepts it. $\endgroup$ – Yuval Filmus Apr 6 '16 at 20:21

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