Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Final State Acceptability
3.
Empty State Acceptability
3.1.
Example 1
3.2.
Example 2
4.
Frequently Asked Questions
4.1.
What type of language is accepted by pushdown automata?
4.2.
What are the approaches used by the PDA to accept a language?
4.3.
What are the types of PushDown automata?
5.
Conclusion
Last Updated: Mar 27, 2024

Pushdown Automata Acceptance

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Theory of Computation

Introduction

Pushdown Automata is a finite automaton with extra memory called stack, which helps Pushdown Automata recognize Context-Free Languages. 

A Pushdown Automata (PDA) can be defined as :

  • Q is the set of states
  • ∑is the set of input symbols
  • Γ is the set of pushdown symbols (which can be pushed and popped from stack)
  • q0 is the initial state
  • Z is the initial pushdown symbol (which is initially present in the stack)
  • F is the set of final states

 Also See, Moore Machine

How language can be accepted using PDA

  • Final State Acceptability
  • Empty State Acceptability

Final State Acceptability

We will discuss how PDA is accepted using the final state.

Let G =(Q, ∑, Γ, δ, q0, Z, F) be a PDA.

The language accepted by P is the set of all strings, acceptable by the final state for any input stack string x can be depicted as follows:

L(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ F} 

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

Empty State Acceptability

Over reading the input string from the initial for some PDA, the stack of PDA gets empty.

For a PDA, G= (Q, ∑, S, δ, q0, I, F), the language accepted by the empty stack will be as follows:

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

Example 1

We have to construct a PDA that accepts L = { wwR | w = (a+b)* }

Solution

PDA for L1

 

Initially, we will insert a special symbol '$' into the empty stack. At the state q2, the w is being read. In-state q3, each 0 or 1 is popped when it matches the input. The PDA will go into the dead state if any other input is given. When we reach the inserted special symbol '$,' we go to the accepting state q4.

Example 2

We have to construct a PDA that accepts L = {0n 1n | n ≥ 0}

Solution

PDA for L

 

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

In the above example, the number of 'a' and 'b' must be identical.

  • Initially, we will insert a special symbol, '$,' in the empty stack.
  • At the state q2, if we encounter input 0 and the top is Null, we push 0 into the stack. This may iterate. And if we encounter input 1 and the top is 0, we pop this 0.
  • At state q3, by chance, we encounter input 1, and the top is 0. We pop this 0. This may also iterate. And if we encounter input 1 and the top is 0, we pop the top element.
  • If the special symbol '$' is encountered at the top of the stack, it is popped out, finally going to the accepting state q4.
     

Also see, Turing Machine in TOC.

Frequently Asked Questions

What type of language is accepted by pushdown automata?

Pushdown automata are used for context-free languages, i.e., languages in which the length of elements is unrestricted, and one element's length is related to the other.

What are the approaches used by the PDA to accept a language?

Two approaches are using which a language can be accepted.

  • Acceptance by final state
  • Acceptance by empty stack

What are the types of PushDown automata?

  • Decider
  • Turing Machine
  • Linear Bounded
  • Nested stack
  • Embedded pushdown

Conclusion

In this blog, we have talked about the following things:

What do you mean by pushdown Automata?

How can a language can be accepted by PDA using the two approaches:

Empty stack acceptability

Final state acceptability

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning!!!

TOC

Previous article
Pushdown Automata(PDA)
Next article
Non-deterministic Pushdown Automata
Live masterclass