The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
58 views
In an intersection between a regular language and a DCFL, we always tend to promote regular language to DCFL and say that the result will be intersection between DCFL and DCFL but since DCFLs are not closed under intersection we say the result will be a CFL. But I feel the answer to the original question should be DCFL because I never came across a language which is an intersection between a Regular language and a DCFL which is not DCFL

Can you write a language which is an intersection between a DCFL and a regular language but not a DCFL.
asked in Theory of Computation by Active (2.7k points) | 58 views
+2

I was having the exact same trouble yesterday :P But after a long discussion concluded that intersection of regular language with any other language(dcfl, cfl, rec, re) is dcfl,cfl,rec,re respectively.

Intersection of languages which are strictly dcfl( i.e. not regular and only dcfl) may or may not be dcfl. What I mean to say is strictly dcfl languages are not closed under intersection.

Please go through the comments here..

https://gateoverflow.in/232494/dcfl-vs-cfl#c232561

+1
Intersection of regular language with any other language is always closed.

Regula $\cap$ DCFL = DCFL

this applies on any other language.

Please log in or register to answer this question.



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

40,903 questions
47,555 answers
146,264 comments
62,304 users