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 A_i_$_h asked Sep 19, 2017 A_i_$_h 443 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments AnilGoudar commented Sep 19, 2017 reply Follow Share Yeah, it involves 3 comparisons and PDA cant do 3 comparisons. plz explain 0 votes 0 votes Arjun commented Sep 19, 2017 reply Follow Share @Anil Never study such "shortcuts" -- or else you will accumulate negatives in GATE. 2 votes 2 votes AnilGoudar commented Sep 19, 2017 reply Follow Share While drawing DPDA ,I got struck in odd number of b's, so i raised the doubt. Thanks for the suggestion Sir. 0 votes 0 votes Please log in or register to add a comment.
Best answer 0 votes 0 votes Here is the DPDA for the given language. In abstract sense, the DPDA presented above proceeds as follows Push all the $a$ into the stack. If the following number of $b$ are even, accept the string by moving to the final state directly. Else proceed to next step. 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 prateekdwv answered Sep 19, 2017 • selected Sep 19, 2017 by A_i_$_h prateekdwv comment Share Follow See all 2 Comments See all 2 2 Comments reply A_i_$_h commented Sep 19, 2017 reply Follow Share a)"we can embed the standard even-odd machine into this DPDA." What does this do?? check if its odd or even?? b) how can you pop a's depending on d's without crossing b values?? 0 votes 0 votes prateekdwv commented Sep 19, 2017 reply Follow Share Improvised my answer, please have a look at it first. a) Yes, it will check whether the count of $b$ in the input string is odd or even. b) We can. We can do that by skipping them and not pushing them into the stack. We will use $b$ from the input string to take the machine from state $q_1$ to $q_2$ and vice-versa. This movement is used to determine if the count of $b$ in the input string is even or odd. 0 votes 0 votes Please log in or register to add a comment.