1
$\begingroup$

Left quotient is defined as below at this link:

Left quotient of $L1$ by $L2$:

$L1\backslash L2:= \{u\in \Sigma^*|vu\in L1$ for some $v\in L2 \}$

Wikipedia defines it as follows:

$L_1\backslash L_2=\{w|\exists x((x\in L_1)\wedge (xw\in L_2))\}$

Q1. I feel both definitions differ. Which one is correct?

Also first link says:

It can be shown that the families of regular, context-free, and type-0 languages are closed under quotient (both left and right) by a regular language. The family of context-sensitive languages does not have this closure property.

whereas wikipedia says:

The quotient of a regular language with any other language is regular.

Q2. I again feel both differ especially in case of regular quotient with CSL. Which one is correct?

Improve this question
$\endgroup$
4
  • $\begingroup$ Your two definitions are the same up to the order of arguments, which apparently isn’t standardized. There is no “right” definition. Both define the same concept, but the notation is slightly different. You can use either, and it’s probably a good idea to explicitly write the definition that you chose. $\endgroup$
    – Yuval Filmus
    Commented Nov 23, 2019 at 19:57
  • $\begingroup$ Regarding your second question, the statements are in complete agreement with each other. One of them just claims more. $\endgroup$
    – Yuval Filmus
    Commented Nov 23, 2019 at 19:58
  • $\begingroup$ isnt first link says regular languages are not closed under right quotient with CSLs, whereas wikipedia says they are closed? $\endgroup$
    – RajS
    Commented Nov 23, 2019 at 20:56
  • 1
    $\begingroup$ It’s the same issue of different order of arguments. The roles of the two languages involved are not the same. $\endgroup$
    – Yuval Filmus
    Commented Nov 23, 2019 at 20:58

1 Answer 1

Reset to default
3
$\begingroup$

All sources agree on the definition of right quotient: $L_1/L_2$ is the set of words which can be extended by a word in $L_2$ to become a word in $L_1$. In other words, $w \in L_1/L_2$ if there exists $x \in L_2$ such that $wx \in L_1$.

If $L_1$ is regular and $L_2$ is any language then $L_1/L_2$ is regular.

For many classes of languages, if $L_1$ belongs to the class and $L_2$ is regular then $L_1/L_2$ also belongs to the class. Examples of such classes include context-free languages and r.e. languages, but not context-sensitive languages. This is definitely the case for languages closed under homomorphism, inverse homomorphism, and intersection with a regular languages. Context-sensitive languages are only closed under $\epsilon$-free homomorphism, which is not enough here.

The left quotient is defined similarly, but we extend the word on the left instead of on the right. The notation is $L_1\backslash L_2$, but authors vary on which part is played by which language. One possible convention (used by Wikipedia) is that we are interested in words which can be extended on the left by a word in $L_1$ to become a word in $L_2$. Another convention (used by your link) reverses the roles of $L_1,L_2$. The alternate notations $L_1 L_2^{-1}$ and $L_2^{-1} L_1$ mentioned in your link are unambiguous. Note how the Wikipedia notation makes a bit more sense here: $L_2^{-1} L_1 = L_2 \backslash L_1$ per the Wikipedia notation, but not per the notation in the link.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Why languages closed under homomorphism, inverse homomorphism, and intersection should be closed under regular quotient? - is their any direct intuitive connection between (homomorphism, inverse homomorphism, and intersection) and regular quotient? $\endgroup$
    – RajS
    Commented Nov 29, 2019 at 9:05
  • $\begingroup$ That’s a nice exercise. $\endgroup$
    – Yuval Filmus
    Commented Nov 29, 2019 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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