Mathematical Foundation of Computer Science

DHARM

294 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

input symbol is not used, and the tape head is not advanced after the move. This type of move

allows the PDA to manipulate the stack without reading the input alphabets.

Thus the transition function δ will be a partial mapping i.e.,

δ : Q × ( Σ ∪ ∈) × Γ → A finite subsets of (Q × Γ*)

For example, let automaton is in state p (∈Q) and ready to scan the input alphabet a ∈

(Σ ∪ ∈) from the tape cell and the stack pointer points the symbol A (∈ Γ*) then choices of

transitions are as follows,

δ (p, a, A) → {(q 1 , γ 1 ), (q 2 , γ 2 ), (q 3 , γ 3 ), ............, (qk, γk)}

where state qi ∈ Q, stack symbol γi ∈ Γ* for all 1 ≤ i ≤ k.

Therefore, we can define a PDA using following tuples,

M = (Q, Σ, Γ, δ, q 0 , Z 0 , F)

where the symbol F ⊆ Q is the set of final states.

Note. Unless stated otherwise, we use lower case letters to denote input alphabets and upper case

letters to denote stack symbols.

If a PDA satisfies following conditions then the PDA will be a deterministic PDA or

DPDA, i.e.,

• For any transition δ(p, a, A), it must have only a single empty (∀p ∈ Q, ∀ a ∈ Σ, ∀A ∈
  Γ*)


• Whenever δ(p, ∈, A) is nonempty then δ(p, a, A) must be empty (∀p ∈ Q, ∀a ∈ Σ, ∀A
  ∈ Γ*)
  (Remember that acceptance power of both model PDA and DPDA will be different)

Instantaneous Descriptions (ID)

ID describes the configuration of the PDA at a given instant with the record of the state and
the stack contents. For example,

(q, ax, γ) 

M

(p, x, Aγ)[∴ δ(q, a, γ) = (p, A)]

This situation is shown in fig. 11.20 (a) and (b).

abb...

M

Z 0

::

H

q Finite Control

...

x

g

Fig. 11.20(a)