317 views

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

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

Which of the following is true?

1. If $L/L'$ is regular then $L'$ is regular.
2. If $L$ is regular then $L/L'$ is regular.
3. If $L/L'$ is regular then $L$ is regular.
4. $L/L'$ is a subset of $L$.
5. If $L/L'$ and $L'$ are regular, then $L$ is regular.

edited | 317 views

A) False because - L = a*b*, L' = a^nb^n Here L/L' = a*. L/L' is regular, but L' is not.

B) True. If L is regular, L/L' is prefix of language. Regular languages are closed under Qoutient/Prefix. So this is correct.

C) 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.

D) 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 )

E) False. Same explanation as C.

selected by
@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.

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)

### gets us a*

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

@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.

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

Let L/L'be X.
Let L'be Y.

L=X.Y can be written?

If X and Y are regular then L is also regular?
according to closure property of regular lang.  L =X.Y  should be regular  IF X AND Y ARE REGULAR

but if we take L/L'= an    ,         L'=bn       then   L= anbn  which is non regular.   .     I am also confused ..