2
$\begingroup$

I am trying to solve this question which appeared in previous exam paper

Can someone help me what i am failing to understand

For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy \in A \text{ for all } y \in B\}$. If $R$ is regular and $L$ is any language, is it always the case that $R\div L$ is regular? Explain.

I am thinking as regular languages closed under right quotient hoping we can use the same proof here but I understand that in right quotient we prove it for any $y$ that belongs to $B$ but for division it is for all $y$ in $B$ .

Also if I have $L_1$ is regular and $L_2$ is context-free, is $L_1/L_2$ Always regular? Always context-free but not always regular? Or not always context-free? Which one is true?

When $L_1$ is context-free and $L_2$ is regular, is $L_1/L_2$ always regular? Always context-free but not always regular? Or not always context-free?

Any ideas will really help me in preparing for my test.

$\endgroup$
  • $\begingroup$ Please pose only one question per post. Note that these are standard closure properties so you should find them in literature and/or the web with little effort. What have you tried and where did you get stuck? $\endgroup$ – Raphael Dec 8 '14 at 11:58
  • 4
    $\begingroup$ Possible duplicate of Closure against right quotient with a fixed language $\endgroup$ – Ran G. Apr 24 '16 at 21:49
2
$\begingroup$

If $L_1$ is regular and $L_2$ is any language, then $L_1 / L_2$ is regular. In fact, the construction of a DFA for $L_1 / L_2$ is almost trivial (with one caveat): It's the same as the DFA for $L_1$, except that the "final" states are the the states which can reach the original accepting states given a string from $L_2$.

Suppose that $M_1 = (Q, \Sigma, \delta, q_0, F_1)$ is the DFA which accepts $L_1$. Then a DFA which accepts $L_2$ is $M_2 = (Q, \Sigma, \delta, q_0, F_2)$, where:

$$F_2 = \left\{ q \in Q : \exists x \in L_2. \delta(q,x) \in F_1 \right\}$$

Now here's the caveat: this proof sketch is not constructive! To turn this into an algorithm requires some way to enumerate or recognise strings in $L_2$, and remember, $L_2$ can be any language.

If $L_1$ is context free and $L_2$ is regular, $L_1 / L_2$ is always context-free (proof left as an exercise), but it is not necessarily regular. (To see why, consider $L_2 = \{ \epsilon \}$.)

EDIT I've just noticed that the definition in the question is different from the usual definition of "right quotient". The usual definition is:

$$A/B = \left\{x\in \Sigma^{*} : \exists y \in B. xy \in A\right\}$$

The definition in the question is:

$$A\div B = \left\{x\in \Sigma^{*} : \forall y \in B. xy \in A\right\}$$

My answer us for the usual definition, because these are standard results. The answers are similar for the definition in the question, except that the construction is slightly different. (See David Smith's comment.)

I suspect there is a typo in the original question.

$\endgroup$
  • $\begingroup$ That definitely helps @pseudonym Much thanks. But what if I have a Regular Language R and any language L will R divides L a regular language? $\endgroup$ – User_1234 Dec 8 '14 at 5:34
  • $\begingroup$ That was my first answer. $\endgroup$ – Pseudonym Dec 8 '14 at 6:16
  • $\begingroup$ what if L1 / L2 = L1. " then which states would we remove from dfa of L1? $\endgroup$ – User_1234 Dec 8 '14 at 6:59
  • $\begingroup$ The DFA to recognize $L_1 \div L_2$ is the same as the DFA which recognizes $L_1$, except that set of final states, say $F'$ is different. In this case, we'd have $F' = \{q \in Q : \forall y \in L_2 \space{} \delta(q, y) \in F\}$, where $Q$ is the set of states of the DFA for $L_1$, $F$ is the set of final states in the DFA for $L_1$, and $\delta$ is the transition function of the DFA for $L_1$. $\endgroup$ – David Smith Dec 8 '14 at 8:20
  • $\begingroup$ @DavidSmith Why not make it an answer, completing that of Pseudonym. $\endgroup$ – babou Dec 8 '14 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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