Question

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?

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top