Question

[20 points] As an example of a PDA look at the one below that accepts the following language (Z is the stack start symbol): {a”br | n >0} U{a}. a, 1; 11 b, 1; a, Z; 12 b, 1 ; 90 q1 q2 1,2; a, Z;À Z: 93 We want to show that the language L below is a CFL by designing the PDA P, defined as P= {{90, 91, 92}, {0, 1}, {x, Z},0,40, 2, {92}}, that accepts it: L = {w w has odd length and the middle letter is 0}. However, the definition of P is not complete. We need to define its transition function. Define the P's transition function () by drawing its graph similar to the example above. Is P a DPDA or NPDA?

Answer 1

solution:

given data:

The transition function (δ) is       Q x {Σ ∪ ∈} x Γ into Q x Γ*. Where Q is the set of states Σ is the set of input symbols ∈ is a null symbol Γ is the set of pushdown symbols The transition are shown below δ(q0,a,Z) =(q1,1Z) δ(q0,a,Z) =(q3, ƛ) δ(q0,ƛ,Z) =(q3, ƛ) δ(q1,a,1) =(q1,11) δ(q1,b,1) =(q1, ƛ) δ(q2,b,1) =(q2, ƛ) δ(q2, , ƛ,Z) =(q3, ƛ)

It is Non-deterministic Push Down Automata(NPDA), Because for the state ‘q0’, input symbol is ‘a’ and Stack symbol is ‘Z’ it was going to two states ‘q1’ and ‘q3’.The transition are shown below. δ(q0,a,Z) =(q1,1Z) δ(q0,a,Z) =(q3, ƛ)

please give me thumb up