Pushdown automata Instantaneous Description

17888

Instantaneous Description (ID) is an informal notation of how a PDA “computes” a input string and make a decision that string is accepted or rejected. Intuitively, PDA goes from configuration to configuration, in response to input symbols (or sometimes ε), but unlike the finite state automaton, where the state is only thing that we need to know about the automaton, the PDA’s configuration involves both the state and the contents of the stack. Being arbitrarily large, the stack is often the more important part of the total configuration of the PDA at any time. It is also useful to represent as part of the configuration the portion of the input that remains.

Thus we can simplify makes a convenient notation for describing the successive configurations of a pushdown automata during the processing of a string. The relevant factors of pushdown configuration notation by a triple (q, w, γ) where;

  • q is the current state of the control unit
  • w is the unread part of the input string or the remaining input alphabets
  • γ is the current contents of the PDA stack

Conventionally, we show leftmost symbol indicating the top of the stack γ and the bottom at the right end. Such a triple notation is called an instantaneous description or ID of the pushdown automata. In short an instantaneous Description (ID) or configuration of a pushdown automaton (PDA) describes its execution status at any time.

A move from one instantaneous description to another will be denoted by the symbol ‘⊢’ thus

(q0, aw, z0) ⊢ (q1, w, yz0)

is possible if and only if

δ(q0, a, z0) ∈ (q1, yz0).

Moves involving an arbitrary number of steps will be denoted by ‘⊢*‘. On occasions where several automata are under consideration we will use ‘⊢M‘ to emphasize that the move is made by the particular automaton M.

Example:

  1. Write down the IDs or moves for input string w = “aabb” of PDA as M = ({q0, q1, q2}, {a, b}, {a, b, Z0}, δ, q0, Z0, {q2}), where δ is defined by following rules:

δ(q0, a, Z0)       = {(q0, aZ0)}     Rule (1)
δ(q0, a, a)         = {(q0, aa)}      Rule (2)
δ(q0, b, a)         = {(q1, λ)}        Rule (3)
δ(q1, b, a)         = {(q1, λ)}        Rule (4)
δ(q1, λ, Z0)       = {(q2, λ)}        Rule (5)
δ(q0, λ, Z0)       = {(q2, λ)}        Rule (6)

Also check string w is accepted by PDA or not?

Solution: Instantaneous Description for string w = “aabb”

(q0, aabb, Z0)   |- (q0, abb, aZ0)            as per Rule (1)
|- (q0, bb, aaZ0)            as per Rule (2)
|- (q1, b, aZ0)                as per Rule (3)
|- (q1, λ, Z0)                  as per Rule (3)
|- (q2, λ, λ)                   as per Rule (5)

Finally PDA reached a configuration of (q2, λ, λ) i.e. the input tape is empty or input string w is completed, PDA stack is empty and PDA has reached a final state. So the string ‘w’ is accepted.

Example 2: Write down the IDs or moves for input string w = “aaabb” of PDA. Also check it is accepted by PDA or not?

Solution: Instantaneous Description for string w = “aaabb”

(q0, aaabb, Z0) |- (q0, aabb, aZ0)           as per transition Rule (1)
|- (q0, abb, aaZ0)           as per transition Rule (2)
|- (q0, bb, aaaZ0)           as per transition Rule (2)
|- (q1, b, aaZ0)              as per transition Rule (3)
|- (q1, λ, aZ0)                as per transition Rule (3)
|- There is no defined move.

So the pushdown automaton stops at this move and the string is not accepted because the input tape is empty or input string w is completed but the PDA stack is not empty. So the string ‘w’ is not accepted.

Previous articlePushdown automata Representation with solved examples
Next articleWhat is SEO-Definition with List of all major search engine
Er Parag Verma
Hello I am Er Parag Verma. I am tech blogger, Professor and Entrepreneur. I am on the mission to change the pattern of learning to make it easy, valuable and advance.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.