Question

Construct a NPDA with transition graph using 4 states that accepts the language L={w: na(w)-nb(w)=2} on Σ={a,b}

subject-- formal language of automata theory.

Answer 1

Push down automata for this language is --

q1 ɛ,a/ € a,Z/aZ b,Z/bZ b,a/€ ɛ,a/ɛ ɛ,Z/Z a,Z/aZ a,b/ɛ qo 93 94 qf b,Z/bZ ɛ,a/ɛ 92

So algorithm goes like this -

First we match equal number of a's with b's and at last we see two more a's left this way we accept the string. Here in this PDA q0 is initial state and qf is accept state.