Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The right quotient of two languages is defined as

$$L_1/L_2=\{ x \mid xy \in L_1 \text{ and } y \in L_2 \}.$$

Example:
$L_1=\{ab,aab,baa\}$ and $L_2=\{b\}.$

I read somewhere that $L_1/L_2=\{a,aa,\varepsilon\}$ but I cannot understand why $\varepsilon$ is contained in the quotient.

share|improve this question
    
$\varepsilon$ is not in $L_1/L_2$. –  A.Schulz Dec 7 '12 at 17:28
    
I see that my title edit was not perfect, but it was likely too nondescriptive to begin with. Perhaps we need to include a proper question in the post too? –  The Unfun Cat Dec 7 '12 at 17:36
add comment

1 Answer 1

In words, your definition says "The right quotient, written $L_1 / L_2$, is defined to be the set of all strings $x$ such that $xy$ is a string in $L_1$ for some string $y$ in $L_2$." According to this definition, the empty string is a member of the right quotient if and only if there is a common string in the two languages. In symbols, $\epsilon \in L_1 / L_2 \iff L_1 \cap L_2 \neq \emptyset$. In particular, this is not the case in your example, hence, the empty string is not in your right quotient.

share|improve this answer
    
simply awesome answer. thanks a lot –  user1771809 Dec 7 '12 at 18:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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