In this example we will discuss NPDA
NPDA are designed when there is no subtle decision like we did in previous example on arrival of 'c'
So now we have to design a machine which can bruteforce the answer.
We have designed the PDA for the problem:
STACK Transiton Function
δ(q0, a, Z) = (q0, aZ) δ(q0, a, a) = (q0, aa) δ(q0, b, Z) = (q0, bZ) δ(q0, b, b) = (q0, bb) δ(q0, a, b) = (q0, ab) δ(q0, b, a) = (q0, ba) // this is decision step δ(q0, a, a) = (q1, ε) δ(q0, b, b) = (q1, ε) δ(q1, b, b) = (q1, ε) δ(q1, a, a) = (q1, ε) δ(q1, ε, Z) = (qf, Z)
Note: qf is Final State
ExplanationLets see, how this DPDA is working:
We will take one input string: "abbbba"
Here a decision tree will get formed to come to the solution.
Thus NPDA is more powerful than DPDA