FOLA-demo55.html

DPDA & Chomsky-like normal form

> ## L:={a^n b : n >= 2}
dpda01:=mkDPDA({q0, q1, q3}, {a, b}, {E, A, C, B, D, Z},
table([(q1, a, B) = [q1, lambda],
(q1, lambda, A) = [q1, [B, A]],
(q1, a, A) = [q1, lambda],
(q1, b, C) = [q1, lambda],
(q0, lambda, Z) = [q1, [E, Z]],
(q1, lambda, D) = [q1, [A, C]],
(q1, lambda, E) = [q1, [B, D]],
(q1, lambda, Z) = [q3, lambda]]),
q0, Z, {q3});
transitionGraph(dpda01);

Plot_2d

> stringVerificationPDA(dpda01,[a,a,a,b]);
stringVerificationPDA(dpda01,[b,a,a,b]);
stringVerificationPDA(dpda01,[a,a,a,b,b]);

(11.1.1)

> ## L:= {a^n b^m : n,m >= 1}
dpda02 := mkDPDA({q0, q1, q3}, {a, b}, {E, A, C, B, D, Z},
table([(q1, b, B) = [q1, lambda],
(q1, lambda, B) = [q1, [D, B]],
(q0, lambda, Z) = [q1, [E, Z]],
(q1, lambda, E) = [q1, [A, B]],
(q1, lambda, Z) = [q3, lambda],
(q1, a, C) = [q1, lambda],
(q1, lambda, A) = [q1, [C, A]],
(q1, a, A) = [q1, lambda],
(q1, b, D) = [q1, lambda]]),
q0, Z, {q3});
transitionGraph(dpda02);

Plot_2d

> stringVerificationPDA(dpda02,[a,a,a,b]);
stringVerificationPDA(dpda02,[a,a,b,b,b]);
stringVerificationPDA(dpda02,[a,a,a,b,a]);

(11.1.2)