Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Components of PDA
3.
Basic Structure of PDA
4.
The Formal Definition of PDA
5.
Terminologies Related to PDA
5.1.
Instantaneous Description (ID)
5.2.
Turnstile Notation
5.3.
Final State Acceptability
5.4.
Empty Stack Acceptability
6.
Example of PDA
7.
Frequently Asked Questions
7.1.
What are the two types of pushdown automata?
7.2.
What is the application of PDA in automata?
7.3.
How many tuples are used for PDA?
7.4.
Can a PDA loop infinitely?
8.
Conclusion
Last Updated: Jul 2, 2024
Easy

Pushdown Automata(PDA)

Author vishal teotia
1 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Pushdown automata are a way to implement context-free grammars(CGF), similar to how to design a  DFA for regular grammars. A DFA can store a limited amount of information, while a PDA can store an infinite amount of information. 

Pushdown Automata is a finite automaton with additional memory called stack that aids in the recognition of Context-Free Languages(CFL).

PDAsPushdown Automata are simply NFAs augmented with external stack memory. PDAPushdown automata can manage memory last-in-first-out with the addition of stacks. An infinite amount of information can be stored in pushdown automata. The stack can be accessed in a limited manner. An element can be pushed onto the top of a stack and removed from the top of the stack using a PDA. The top elements of a stack must be removed to read an element.

PDAs are more powerful than FAs. It can also accept the Llanguages that are acceptable by FA can also be accepted by PDA. Additionally, PDA accepts a class of languages that FA cannot. For this reason, PDA is superior to FA.

Also see, Turing Machine in TOC.

Components of PDA

Components of a Pushdown Automaton (PDA):

  • States: Finite set of states that the PDA can be in at any given time.
     
  • Alphabet: Set of input symbols that the PDA reads.
     
  • Stack Alphabet: Set of symbols that can be pushed to or popped from the stack.
     
  • Transition Function: Defines the PDA’s actions based on the current state, input symbol, and stack top symbol. It specifies the next state, the symbol to push or pop, and the remaining input.
     
  • Start State: The initial state of the PDA where computation begins.
     
  • Start Stack Symbol: The initial symbol on the stack.
     
  • Accept States: Set of states that signify the PDA has accepted the input if it ends in one of these states.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Basic Structure of PDA

A pushdown automaton is, in essence,

"A stack" + "a finite state machine."

A pushdown automaton is made up of three parts: an infinite-size stack, a control unit, and an input tape.

The stack head examines the stack's top symbol. A stack performs two tasks :

  • Push: At the top, a new sign is inserted.
  • Push: The symbol at the top is read and eliminated.

It is possible for a PDA to read input symbols or not, but every transition requires it to read the top of the stack.

Input tape: There are many cells or symbols on this tape. A single symbol may only be entered at a time using the input head, which is read-only.

Finite control: The finite control contains a pointer pointing to the symbol currently being read.

Stack: A stack is a structure in which items are pushed and pulled from one end only. It can have infinite size. Items are temporarily stored on the stack in a PDA.

Read About - Simplification of CFG

The Formal Definition of PDA

In formal terms, a PDA is a 7-tuple (Q, ∑, S, δ, q0, I, F)

  • The number of finite states is Q
  • where ∑ is the input alphabet
  • whileis the stack symbol
  • δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S*
  • Initial state is q0 (q0 ∈ Q)
  • andis the first stack top symbol (I ∈ S)
  • whereis the set of accepted states (F ∈ Q)

Terminologies Related to PDA

Instantaneous Description (ID)

An ID is an informal notation of how a PDA computes an input string and decides whether it should accept it or reject it.

Instantaneous descriptions have the form (q, w, α) where:

The current state is described by q.

The rest of the input is described by w.

α describes the contents of the stack, with the top at the left.

Turnstile Notation

"Turnstile" notation is used to connect IDs representing one or more movements of a PDA. The turnstile symbol "⊢" indicates the process of transition.

Consider a PDA (Q, ∑, S, δ, q0, I, F). The following turnstile notation can be used to represent a transition mathematically: −

(p, aw, Tβ) ⊢ (q, w, αb)

The input symbol 'a' is consumed when moving from state to state q, and the top of the stack 'T' is replaced by a new string 'α'.

Final State Acceptability

The final state acceptance of a string occurs after the PDA is ready after reading the entire string. The starting state can be moved in a way that eventually leads to a final state with any stack value. We don't care about the stack values as long as we get to the final state.

Empty Stack Acceptability

The PDA accepts a string after it has emptied its stack after reading the entire string.

The language accepted by the empty stack of a PDA (Q, ∑, S, δ, q0, I, F) is 

L(PDA) = {w | (q0, w, I) ⊢* (q, ε, ε), q ∈ Q}

Example of PDA

 Implement a PDA that accepts L = {0n 1n | n ≥ 0}

This language accepts L = {ε, 01, 0011, 000111, ............................. }

The numbers 'a' and 'b' in this example have to be the same.

  • The empty stack was initially filled with the special symbol '$'.
  • As soon as we encounter input 0 at state q2, if the top is null, we push 0 into the stack. We may repeat this. Similarly, if input 1 is encountered at state q2, we pop 0 from the stack.
  • If input 1 is encountered at state q3 and the top is 0, we pop this 0. Iteration may also take place. If input 1 is encountered and the top is 0, we pop the top element.
  • Upon encountering the special symbol '$' at the top of the stack, it is popped out, and it finally moves to the accepting state q4.

You can also read about - Moore Machine

Frequently Asked Questions

What are the two types of pushdown automata?

There are two types of Pushdown Automata (PDA): Deterministic Pushdown Automata (DPDA) and Nondeterministic Pushdown Automata (NPDA). DPDA has at most one possible transition for a given state and input, ensuring deterministic behavior, whereas NPDA allows multiple transitions, enabling nondeterministic behavior and greater flexibility in language recognition.

What is the application of PDA in automata?

Pushdown Automata (PDA) are primarily used to recognize context-free languages, which are crucial in the design and implementation of programming languages and compilers for syntax checking.

How many tuples are used for PDA?

PDA does not have a single state. Specifically, it is a 6-tuple that contains the transition function.  

Can a PDA loop infinitely?

The PDA will either halt within finitely many steps or will loop forever

Conclusion

Our blog has covered the following topics:

  • Pushdown automata - what does that mean?
  • Terminologies Related to PDA
  • The following two approaches can be used to accept a language by PDA: Empty stack acceptability, Final state acceptability.
  • We have gone through an example also.

Check out this link if you want to explore more about Theory of Computation.

Check out this article - Converting NFA to DFA

 Arden's theorem

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Live masterclass