2,017 views
0 0 votes

If  $L_1$ is DCFL and $L_2$ is context free language. Consider the below given statements

Which is correct between these and why ? (S1 is correct.. but why ??) . I couldn’t understand the explanation given in the solution..

1 Answer

1 1 vote

S1:  $\bar{L_{1}}$  - ${L_{2}}$  : True
it can be written as $\bar{L_{1}}$  $_{\bigcap }$ $\bar{L_{2}}$   , L2 is given as CFL and CFL is not closed under complementation and it will fall in 1 higher class of language CSL.

S2: $\bar{L_{1}}$  - $\bar{L_{2}}$ : False

it can be written as  $\bar{L_{1}}$  $_{\bigcap }$ ${L_{2}}$ , which is again not closed under intersection/union.

 

If L1 and L2 are CFLs, then L1 ∩ L2 may not be a CFL.

Both CFL and DCFL are closed under intersection with regular sets.

• reshown by
Position:
Show:

Related questions

3 3 votes
1 1 answer
2.7k
2.7k views
logan1x asked May 10, 2019
2,723 views
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
0 0 votes
1 answers 1 answer
796
796 views
Shubham Kumar Gupta asked Dec 24, 2017
796 views
Qus: If L1=DCFL, L2= DCFL then L1-L2=?Sol: We can see from the above figure that DCFL’s are not closed under difference operation so L1-L2 = L3, is not a DCFL.The doubt i...
2 2 votes
2 2 answers
3.9k
3.9k views
rahul sharma 5 asked Nov 21, 2017
3,916 views
Following is the PDA that accept equal number of a and b.How can this be converted to DPDA? When stack top is Z,that it can read epsillon or a or b,which can create choic...
1 1 vote
1 1 answer
2.9k
2.9k views
rahul sharma 5 asked Jul 31, 2017
2,854 views
How many stacks are available with DPDA and NPDA? I assume it is 1 with DPDA and n with NPDA where n is some constant.Assume i have a language ,over alphabet a,b,c,dL=( W...