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.

plz explain this part!

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

For $A, B ⊆ Σ^*$, define

$A/B = \{x ∈ Σ^* | ∃y ∈ B, xy ∈ A\}$

If $L$ is a $CFL$ and $R$ is regular, then $L/R$ is

- Regular
- $CFL$ but not regular
- Recursive but not $CFL$
- None of the above

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,861 questions

47,532 answers

145,982 comments

62,293 users