Peter linz ex 4.3 ques 4

Question

Comments

questions from a-b, there is one comparission between (n+l) and k ===> DPDA

question c, there is one comparission between either (n and l) or ( l and k ) ===> NPDA

question d, there is one comparission between n and l  ===> DPDA

question e, there is one comparission between a and b  ===>DPDA

question f, there is one comparission required but it can't accomplished by stack, therefore we required queue ==>CSL  ===> NTM

question g, there is one comparission required but it can't accomplished by stack, therefore we required queue ==>CSL  ===> NTM

---

in case of first how we apply push and pop apply?

---

@Chandrabhan Vishwa 1

let take z as stack symbol, 

on getting a on empty stack ===> push z in to the stack, change state

on getting a on z ===> push z in to the stack, don't change state

on getting b on z ===> push z in to the stack, change state

on getting b on z ===> push z in to the stack, don't change state

on getting a on z ===> pop z from the stack, change state

on getting a on z ===> pop z from the stack, don't change state

check for empty stack on getting a ( if k > (n+l) ), check for empty stack on getting empty string ( if k = (n+l) ),