Thnq L w1cw2w1 w2 belongsto a b w1 neq w2R design NPDA diag

Thnq

L = {w_1cw_2:w_1, w_2 belongsto {a, b}*, w_1 neq w_2^R}. design NPDA diagram

Solution

Npda N = (K, , , , s, F), where K = {s0, s1, d, f}, = {a, b}, F = {f}, and as the set of following rules accepts L.

((s0, a, e),(s0, a))

((s0, b, e),(s0, b))

((s0, c, e),(s1, e))

((s1, a, a),(s1, e))

((s1, b, b),(s1, e))

((s1, a, b),(d, e))

((s1, b, a),(d, e))

((d, e, a),(d, e))

((d, e, b),(d, e))

((d, a, e),(d, e))

((d, b, e),(d, e))

((d, e, e),(f, e))