The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+8 votes
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.

 

asked in Theory of Computation by Veteran (42.4k points)
edited by | 317 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 (46.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*

 

+5 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.4k 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 (3.2k 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



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,944 questions
36,792 answers
91,050 comments
34,688 users