TIFR CSE 2013 | Part B | Question: 6

Question

Let $L$ and $L'$ be languages over the alphabet $\Sigma $. The left quotient of $L$ by $L'$ is

$L/L'\overset{{def}}{=} \left\{w \in \Sigma^* : wx ∈ L\text{ for some }x \in L'\right\}$

Which of the following is true?

• A. If $L/L'$ is regular then $L'$ is regular.
• B. If $L$ is regular then $L/L'$ is regular.
• C. If $L/L'$ is regular then $L$ is regular.
• D. $L/L'$ is a subset of $L$.
• E. If $L/L'$ and $L'$ are regular, then $L$ is regular.

Answer 1

1. False because - $L = a^*b^*$, $L' = a^nb^n$ Here $L/L' = a^*. L/L'$ is regular, but $L' $ is not.
2. True. If L is regular, $L/L'$ is prefix of language. Regular languages are closed under Qoutient/Prefix. So this is correct.
3. False $L' =$ Empty set. Then $L/L'$ is Empty set whatever $L$ is. Here $L$ can be say $a^nb^n$. See defination of $L/L'$ to see why $L/L'$ should be empty set.
4. False because $L/L'$ can accept prefixes of string of Language $L$, which may or may not be accepted by $L$ itself. So $L/L'$ is not subset. ( It is not Superset either , because $L' $ can be empty set )
5. False. Same explanation as C.

Answer is B.

Comments

@Akash please tell me for case b, If L is regular then we assume that L = {a*b* } is regular

and L' = {a^n b^n | n >=0} then L/L' are not regular please correct me if i am wrong.

---

@brij, No L / L' is regular.
L = {a*b*}.
L' = {a^n b^n | n >= 0}

Then L / L' = {a*b*}. which is regular.
L' contains $\in$. Take any string in L say w. Then do w.$\in$ = w which belongs to L.
If you take any other string from L' say ab. Then take any string from $\sum$ * say w. Then do w.ab this will not belong to L unless w is $\in$. So it will not be present in L/L'.

---

Thanks @Hemant for greate explaination

Early according to me L/L' will be {a^nb^m | n != m} which is the wrong assumption.

---

@ Hemant Parihar

Then take any string from ∑ * say w. Then do w.ab this will not belong to L unless w is ∈. So it will not be present in L/L'.

 w can be aaaaab

L/L'=aaaa

I can't understand why you said w has to be ∈ ?

---

@VS yes you are right. w can be any string of a^n b^n. Thank you for pointing out.

---

@VS @Hemant Parihar May you please tell, how in option a)

L1/L1’ = a*b*/ aⁿ bⁿ  

gets us a*

 

---

Can someone please explain the (c) part of the answer?

What I understood is that the concatenation with an empty set results in the empty set(phi) and which is the part of every set, so this confirms that L can be anything. My doubt is how can we say that L/L' should be an empty string, but it can be anything.

According to the definition which I understood L/L' contain all the strings w which are the prefix to some string x which belong to L' and the concatenation of w and x belongs to L.

---

On option B: Does the language L/L’ contain all the prefixes of L? Is a language, which contains only some of the prefixes of a regular language, also regular?

Answer 2

Let L = $a^nb^nc^n$ Non regular
       L'= $b^nc^n$ non regular
then L/L' = $a^n$ regular 

option a) False since L/L' = $a^n$ regular and L' is not

option b) True if L is regular then whatever we remove from it it will remain regular 
                        regualr language are closed under quoitent 
                        e.g. L=$a^*b^*$ L'=b* L/L' = $a^*$ regular
                        
option c) since L/L' = $a^n$ regular and L is not

option d)L/L' is subset of L false L dont have any production like a or aa or ....

option e) False Let L' = $b^n$ regular L=$a^nb^n$ non regular but L/L' = $a^n$ regular 
 

Comments

@Umang please tell me for case b, it is given If L is regular then we assume that L = {a*b* } is regular

and L' = {a^n b^n | n >=0} then L/L' are not regular please correct me if i am wrong.

---

@Umang Raman 

Let L = a^nb^nc^n Non regular 
       L'= b^nc^n non regular

bhai yeh sach mein hai L' yahan arbirtary choose kiya hai like to show a counter example?