The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
71 views

For $A, B ⊆ Σ^*$, define
$A/B = \{x ∈ Σ^* | ∃y ∈ B, xy ∈ A\}$
If $L$ is a $CFL$ and $R$ is regular, then $L/R$ is

  1. Regular
  2. $CFL$ but not regular
  3. Recursive but not $CFL$
  4. None of the above
asked in Theory of Computation by (123 points)
edited by | 71 views

1 Answer

+2 votes
Best answer

Answer : D

$L/R$ where $L$ is CFL and $R$ is Regular, then $L/R$ will definitely be CFL because CFL's are closed under right Quotient operation with Regular languages. (See proof here if interested :  https://cs.stackexchange.com/questions/20090/closure-of-cfl-against-right-quotient-with-regular-languages )

Though, CFL's are closed under right Quotient operation with Regular languages, But this only means that CFL under right Quotient operation with Regular languages will be CFL. It doesn't mean that It can't be Regular.

For instance, If the given CFL itself is Regular then result will also be regular.

Or Even if $L$ is Non-regular CFL, then also $L/R$ can be Regular.

For example, Consider this :

$L = \left \{ a^nb^n \,\,|\,\,n \geq 1 \right \}$  and $R = \left \{ b^n \,\,|\,\,n \geq 1 \right \}$

then $L/R = \left \{ a^n \,\,|\,\,n \geq 1 \right \}$ Which is Regular.

So, the correct answer for the asked question will be "$L/R \,\,is\,\, CFL$. Hence, Option D is correct.

answered by Boss (24.1k points)
selected by
0

For example, Consider this :

L={anbn|n≥1}L={anbn|n≥1}  and R={bn|n≥1}R={bn|n≥1}

then L/R={an|n≥1}L/R={an|n≥1} Which is Regular.

 

Deepakk Poonia (Dee)

plz explain this part!

Related questions

0 votes
0 answers
7
asked Oct 4, 2017 in Digital Logic by AnilGoudar Active (4.7k points) | 82 views
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
49,408 questions
53,589 answers
185,805 comments
70,871 users