edited by
2,946 views
27 votes
27 votes

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?

  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 by

2 Answers

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

edited by
27 votes
27 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 

 

Answer:

Related questions