CFL or DCFL?

Question

Let $L = \{a^mb^nb^kd^l  (n+k) \text{ is odd only if } m = l; m, n, k, l > 0\}$. Which of the following is true about $L$?

• A. $L$ is CFL but not DCFL
• B. $L$ is regular but not CFL
• C. $L$ is DCFL but not regular
• D. None of these

Comments

hey i understood why dcfl from the explaination from a previous thread u can check it too :
 

We can design the satck like normal DCFL for amdl(as m=l it would be like a^nb^n)

and for bn+k we can design a stack like for one input it will insert a value let 'X' in stack and encountering a b again it will pop 'X' So when the stack iscontained the last value inserted at the time of am then it is understandable that n+k=even

So we can transit to a next state when stackhas new one value in the second state i.e ODD

so all moves are obvious and only one transition is possible for each case

it is DCFL but not regular

If u have a problem i'll help u

---

Please draw its dpda.

---

what will be the ans if n+k=even rest of all same.

Answer 1

Given, m, n, l, k > 0

                                ----------- [CONSTRAINT 1]

Also, (n+k) is odd only if (m=l)

                                ------------ [CONSTRAINT 2]

Therefore, (n+k) is odd --> (m=l)

Therefore, if (n+k) is odd, we have to check if (m=l), only then will the word be accepted.

However, if the (n+k) isn't odd, we don't care if (m=l) or not, the word will be accepted (provided CONSTRAINT 1 is satisfied, i.e. there is at least 1 d).

The transition diagram is given below.

NOTE

To check whether (n+k) is odd or not, we do the following-

1. For every even occurrence of b, simply make a transition from state q1 to state q2 while popping the top of the stack.

2. For every odd occurrence of b, simply make a transition from state q2 to state q1 while pushing symbol X onto the stack.