L1 = {ca^nb^n} ∪ {da^nb^2n} L2 = {a^nb^n c} ∪ {a^nb^2n d}

Question

$L_1 = \left\{ca^nb^n\right\} \cup \left\{da^nb^{2n}\right\}$

$L_2 = \left\{a^nb^n c\right\} \cup \left\{a^nb^{2n} d\right\}$

1. Both are DCFL’s
2. Both are NCFL’s
3. L1 is DCFL, L2 is NCFL
4. L1 is NCFL, L2 is DCFL

Answer 1

L1 is DCFL because der is one to one comparison between no of a and b and  c & d are used to identify which {ca^nb^n} ∪ {da^nb^2n} sub language execute first.

i think L2 is NCFL because union of two DCFL always be an CFL but der is no CLUE to identify which  sub language executes first thats why it is not DCFL..

Comments

"sub language execute first" what do you mean by that?

---

see soln by Aditya .U will get clue

Answer 2

For L1 :

{q₀ ,c} = {q₁}

{q₀ ,d} = {q₂}

{q₁ ,a, Z₀} = {q₁ , aZ₀ }

{q₁ ,a, a} = {q₁, aa }

{q_{1 ,}b,a} = {q₃,∈ }

{q_{3 ,}b,a} = {q₃,∈ }

{q₃ ,∈,Z₀} = {q_f ,∈}

{q₂ ,a, Z₀} = {q₂ , aaZ₀ }

{q₂ ,a, a} = {q₂, aaa }

{q_2 ,b,a} = {q₄,∈ }

{q_4 ,b,a} = {q₄,∈ }

{q₄ ,∈,Z₀} = {q_f ,∈}

Similarly you can construct for L2.. So both are NCFL..

Comments

Both are NCFL, but we can make DPDA for $L_1$ making it DCFL.

---

how ?

---

what you gave is DPDA rt?

---

Initially i thought L1 is NCFL but i think using c & d we can make a decision about which path to take. So we can be in one path at a single point of time. So its a DCFL.

But there is no such choice in L2(i.e. parallel processing is required). Hence its a NCFL.