Question

Build a NPDA to recognize the language

{a^(m1)b^(n1)···a^(mk)b^(nk): k≥1; ∀l, 1 ≤ l ≤ k, ml ≥1∧nl ≥ 1; ∃i, j,1 ≤ i,j ≤ k, mi=nj}

These are the strings of alternating “runs” of a’s and b’s such that there is (at least) one run of a’s with the same length as one run of b’s.

Answer 1

Design a Non-Deterministic PDA for accepting the above language L.

= {a,b,z}

z = Start symbol

q₀ = Initial state

q_f = Final state

= perform pop operation

[Attaching the imag consisting of NPDA state diagram and the transition funtion.]