Ace Test Series: Theory Of Computation - Closure Property

Question

please explain:

Comments

All options are wrong, because if we see Chomsky hierarchy then every DCFL is CFl and every CFL is CSL hence every DCFL is also CSL, but here just reading the options one can say D is the answer.

Coming to explanantion:-

L1 is regular

L2 is CFL but not DCFL .

Reg ^ CFL = CFL not DCFL.

so answer should be D) None of these.

---

L₂ is not DCFL? Any reason.

---

0ⁿ1⁺0ⁿ this one is DCFL and 0ⁿ1^*0ⁿ is not DCFL but CFL.

Did you get this?

---

when 0ⁿ0ⁿ  is there is there any comparision needed.?

i have two cases:

1. when no 1 is come when push and accept i.e. 0²ⁿ

2. when 1 come till 1 push and after 1 pop for matching. 

it is REG union DCFL = DCFL isnt?

---

But at the starting of the string how you will come to know that string may or may not contain 1?

---

@subhanshu : $L_2 \text{is undoubtly DCFL hence CFL}$

$\Rightarrow \text{push 0 on seeing it }$

$\Rightarrow \text{on seeing 1 move to other state without pushing it as it is a indication of pop state entry }$

$\text{on seeing every 0 pop the content of stack}$

---

@sourav. it is 1* not 1+ so it is not necessary that every string will contain 1 in it.

---

@subhanshu : yes you are correct , i missed $o^{n}1^{*}0^{n}$, it will be non deterministic then.

Thanks

---

thanks everyone ,i was thinking i was doing some mistake .

Answer 1

All three options are wrong.
if you follow Chomsky hierarchy, you get that all DCFL is also CFL.
And a CFL is also a CSL.

L = L₁ intersection L₂

L = 0ⁿ1*0ⁿ 

So L is CFL as well as CSL ,REL but not RL.
As 0ⁿ1⁺0ⁿ is DCFL
So option is D.