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 405 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.