Regular and CFL

Question

Let L={aⁱ b^j c^k ┤|if j is odd then i=k} where i,j,k>0. Which of the following option is true about L?

1.   L is CSL but not CFL
2.   L is CFL but not DCFL
3.   L is regular
4.   L is DCFL but not regular
    

Comments

L= $a^{i}b^{j}c^{k}$ | (i<=j) or (j<=i) , j=k} is CFL?

I think it is not CFL, pls correct me if I'm wrong.

---

yes this is CFL...and also DCFL

..$L= aⁱb^jc^k | (i<=j) or (j<=i) , j=k}$

here i and j would be independent...like this...we can write it like this too

{L= a^mbⁿcⁿ} ...u see:)

---

@hs_yadav  I did not understand how it is CFL. How can we compare i, j and k? Please explain using stack.

Answer 1

L = {$a^ib^jc^k$ | if j is odd then i=k, where i,j,k >0}

This language can be divided into two parts.
i. when j is odd
ii. when j is even

i. L1 = {$a^nb(bb)^*c^n | n>1$}, and this language is DCFL

ii. if J is even then a's and c's can be anything either equal or notequal.
    L2 = {$a^p(bb)^*c^q | p,q >0$}, L2 is Regular

$\text{L = L1 U L2 = DCFL U Regular = DCFL}$

Comments

I can't visualize the stack implementation of the above language.. Little help Plz

---

@vaibhav this DCFL doesn't satisfy prefix property as when J is even then
'aabbcc' is in the language and 'aa' is also in the language, and 'aa' is the proper prefix of 'aabbcc'.
Hence we can not construct a DPDA with empty stack acceptance for this language, So, construct a DPDA for this language with final state acceptance. 

---

@ Manu Thakur what about the language 

L1=canbn DPDA

L2=anbnc NPDA   it cannot be accepted by stack but we can accept it by final state acceptance so it should be DPDA