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

I think the question is DCFL

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

 

correction required , I am not 100%sure

 

---

b^n+k , where n + k = odd.

so, it will be bbb,bbbbb,bbbbbbb,bbbbbbbbb.........

Hence, middle part is regular , we don't bother for it . Now, what is left ==> a^md^l  where m = l

Hence, DCFl. u r right

---

Tahnks Kapil

---

option b is wrong definitely. i m confuse between a and c.

---

Here comaparision between a and d and [make b as odd always ( skip operation for that) we have DFA for that] and Push for every a and Pop one a for every d.

---

I am getting the a & d comparison part not about b.Thats why i asked fir a diagram if u can upload it.

---

I think this one is CFL but not DCFL:-

which makes option a) as true.

---

I had also got CFL.But the answer is  given DCFL.That's why i posted the question

---

because of transition 1 to 4 it is not dcfl but cfl.

---

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

I think the question is DCFL

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

and for b^n+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 a^m 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

correction required , I am not 100%sure

Answer 2

push all a's to the stack. now check if number of b's are odd or not which can be checked by a loop.if they are not odd u can simply accept the string.. if they are odd check if number if a's=number of d's by popping one a for every 'd' u encounter. if m=l the accept, else reject
hence its clearly DCFL

Comments

 When no of b's = odd and (d's !=a's ) which should be accepted.

why? b's=odd it means definitely d's shud be equal to a's according to the question. if number of b's=odd and a's!=d's then it shud be rejected.

 case-2:When no of b's even and ( no of a's = no of d's. ). Which should be rejected?
why? we only care about the cases where b's are odd.. b's are not odd, we can simply accept it.
question says "(n+k)=odd only if m=l,"
if (n+k) is not odd we need not check for m=l

---

It can also be done as => (If there is doubt)

If (m=l) then (n+k)=odd ,i.e

A -> B or A' union B

So, language becomes,

L = { a^mbⁿc^kd^L   |   M != L }  union  { a^mbⁿc^kd^L   |    (n+k) != odd }

L = DCFL

---

kapil a,b,d used in language only

Answer 3

It is not exact but may be idea is clear from this pic . since their is comparison b/w a and d so can't be regular.

Correction : On second state null, zo ,accept

Answer 4

C option 

Answer 5

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.