Language DCFL?

Question

$L_{1}=\left \{ 0^{m}.1^{n}.2^{m}.3^{n} \right |n,m>0\}$

$L_{2}=\left \{ a^{i}.b^{j}.c^{k}.d^{l} \right |i+k=j+l\}$

which one DCFL?

Refrence :https://gateoverflow.in/15327/context-free-or-not

---

I think both not DCFL, but need valid reason for it

Comments

L1 is not CFL as well right, It must be CSL.

---

L1 is not DCFL, but L2 is.

---

how?

---

i+k = j+l

==> i+k-j = l ===> i - j + k = l

push x's for each a, then pop x's for each b, if stack is empty then push y for each b,

push x's for each c, if top of stack is x,

if top of stack is y, then pop y for each c

if top of stack is empty, then push x for each c

pop x's for each d, if stack empty at final, then accept it !

---

@Shaik Masthan

I only want to know, which one DCFL and which one not?

---

mam, 1st is not CFL, But 2nd one is DCFL, in your previous comment you asked how, that's why i commented the explanation

Answer 1

1. First 1 is not CFL because it cannot be realised using a PDA. It's in fact a CSL langalan accepted by Turning machine.

2. Given condition i + k = j + l ;

It can be written as i - j =  l - k. Push all A's and Pop for every B's remaining is i - j in the stack. Similarly push all C's and Pop for every D remaining is l - k. It can be compared. It's a DCFL.

Please correct me if wrong..!