Pushdown Automata Introduction - Automata Theory

What is the basic Structure of PDA?

A pushdown automaton is a process that includes a context-free grammar in a same way we design DFA for a regular grammar. A DFA includes a finite amount of information, but a PDA includes an infinite amount of information.

Generally a pushdown automaton is −

"Finite state machine" + "a stack"

A pushdown automaton includes three components −

  • an input tape,
  • a control unit, and
  • a stack with infinite size.

The stack head scans the top symbol of the stack.

A stack performs two operations −

  • Push − a new symbol is added at the top.
  • Pop − the top symbol is read and removed.

While,A PDA may not read an input symbol, as it has to read the top of the stack in every transition.

pda

A PDA is generally explained as a 7-tuple (Q, ∑, S, δ, q0, I, F) −

  • Q is the finite number of states
  • ∑ is input alphabet
  • S is stack symbols
  • δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S*
  • q0 is the initial state (q0 ∈ Q)
  • I is the initial stack top symbol (I ∈ S)
  • F is a set of accepting states (F ∈ Q)

Below mentioned diagram explains a transition in a PDA from a state q1 to state q2, labeled as a,b → c −

transition_in_a_pda

This indicates at state q1, if we meet an input string ‘a’ and top symbol of the stack is ‘b’, then we pop ‘b’, push ‘c’ on top of the stack and move to state q2.

What are the Terminologies Related to PDA?

Instantaneous Description

The instantaneous description (ID) of a PDA is marked as a triplet (q, w, s) where

  • q is the state
  • w is unconsumed input
  • s is the stack contents

Turnstile Notation

The "turnstile" notation is meant to be connect different pairs of ID's which represents more than two moves of a PDA. This process of transition is expressed with the turnstile symbol "⊢".

Let’s consider a PDA (Q, ∑, S, δ, q0, I, F). Following transition is mathematically represented by the following turnstile notation –

This is applicable where the transition from state p to state q, the input symbol ‘a’ is consumed, and the top of the stack ‘T’is replaced by a new string ‘α’.

Note − If we want zero or more moves of a PDA, we have to use the symbol (⊢*) for it.

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics