405 views
0 votes
0 votes
L = { a^m b^n b^k d^l |(n+k)=odd only if m=l; m, n, k , l>0}. Which is true?

a)CFL but not DCFL

b)regular but not CFL

c)DCFL but not regular

d)none

1 Answer

Best answer
0 votes
0 votes

Here is the DPDA for the given language.

In abstract sense, the DPDA presented above proceeds as follows

  1. Push all the $a$ into the stack.
  2. If the following number of $b$ are even, accept the string by moving to the final state directly. Else proceed to next step.
  3. For every $d$ pop one $a$ from the stack. If all the $d$ from input string are exhausted, and the stack is empty, accept the string by moving the machine to the final state.

HTH

selected by

No related questions found