NPDA for accepting the language L = {aibjckdl | i==k or j==l,i>=1,j>=1}

Problem –
L = {abcd, aabccd, aaabcccd, abbcdd, aabbccdd, aabbbccddd, ......} 
Explanation –
 = { a, b, c, d, z } 
Approach used in the construction of PDA –
  • For i==k : Whenever ‘a’ comes, push it in stack and if ‘a’ comes again then also push it in the stack.After that, if ‘b’ comes not do any operation. After that, when ‘c’ comes then pop ‘a’ from the stack each time.After that, if ‘d’ comes not do any operation.
  • For j==l : Whenever ‘a’ comes, not do any operation.After that, if ‘b’ comes push it in stack and if ‘b’ comes again then also push it in the stack. After that, when ‘c’ comes not do any operation.After that, if ‘d’ comes then pop ‘b’ from the stack each time.
Stack transition functions –
(q0, a, z)  (q1, az)
(q0, a, z)  (q3, z)
(q1, a, a)  (q1, aa)
(q1, b, a)  (q1, a)
(q1, c, a)  (q2, ) 
(q2, c, a)  (q2, ) 
(q2, d,  )  (q2, ) 
(q2, , z)  (qf1, z)   
(q3 a, z)  (q3, z)
(q3 b, z)  (q3, bz)
(q3 b, b)  (q3, bb)
(q3 c, b)  (q3, b)
(q3, d, b)  (q4, ) 
(q4, d, b)  (q4, ) 
(q4, , z)  (qf2, z)