edited by
435 views
0 votes
0 votes

Doubt 1:

CFL $\cap$ DCFL = CFL 

CFL – Context Free Languages

DCFL – Deterministic Context Free Languages

Can you prove above expression

 

Doubt 2:

Consider L$_{1}$ = Language generated by a machine M1

L$_{2}$ = Language generated by a machine M2

Machine can be – FA, PDA, LBA, or TM

Assuming Machine M2 is more powerful than M1 

Let L$_{3}$ = L$_{1}$  $\cap$  L$_{2}$

Now can we say that  L$_{3}$ can be generated by Machine M2

For eg:

L1 = Context Free Language (i.e Generated by NPDA)

L2 = Recursively enumerable language (i.e Generated by TM)

Now can we say  L$_{1}$  $\cap$  L$_{2}$ is Recursively Enumerable Language i.e it can be generated by a TM

 

Doubt 3:

Non Recursively Enumerable Language $\cap$ Any language = Non Recursively Enumerable Language

Is this statement correct/always true?

edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
UltraRadiantX asked Oct 9, 2021
450 views
let L = “CFL but not REGULAR”, Can we get complement of L as CFL?Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, it...
1 votes
1 votes
1 answer
2