in Theory of Computation edited by
159 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?

in Theory of Computation edited by
159 views

4 Comments

it means if L1 regular language then L2 CFL or any other language?
0
0

@Kabir5454 can u plz explain in doubt 1 how one is cfl and other is dcfl in ur given example ?

0
0

@shikhar500

the example give by me in doubt 1 is not correct .

I have taken both DCFL and show their intersection CSL .

The problem should have defined clearly as 

they want intersection of set of dcfl language and set of CFL language or they want for any particular language .

 

0
0

Please log in or register to answer this question.

Related questions