GATE CSE
First time here? Checkout the FAQ!
x
+8 votes
264 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.

 

asked in Theory of Computation by Veteran (38.8k points)  
edited by | 264 views

3 Answers

+6 votes
Best answer
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.

 

Answer :- B.
answered by Veteran (43.8k points)  
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.

@ 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*/ an bn  

gets us a*

 

+4 votes

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 

 

answered by Veteran (15.2k points)  
@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?

–2 votes
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?
answered by Loyal (2.9k points)  
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 ..

Related questions



Top Users Sep 2017
  1. Habibkhan

    7096 Points

  2. Warrior

    2574 Points

  3. Arjun

    2416 Points

  4. rishu_darkshadow

    2402 Points

  5. A_i_$_h

    2204 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1760 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,115 questions
33,691 answers
79,846 comments
31,098 users