Table of contents
1.
Introduction
2.
Non-Deterministic Pushdown Automata
2.1.
Stack in Non-Deterministic Pushdown Automata
2.2.
Steps in Transition
3.
Formal Definition of NDPAs
4.
Frequently Asked Questions
4.1.
What is meant by regular expression?
4.2.
Write a regular expression for a set of vowels?
4.3.
What are Regular Language and Regular Grammar?
5.
Conclusion
Last Updated: Mar 27, 2024

Non-deterministic Pushdown Automata

Author Anant Dhakad
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
TOC

Introduction

Pushdown Automata is a finite automaton with additional memory known as a stack that aids in the recognition of Context-Free Languages. In this article, we discuss a type of Pushdown automata, i.e. Non-deterministic Pushdown Automata. We will also learn about its formal definition.

Also See, Simplification of CFG

Non-Deterministic Pushdown Automata

Non-deterministic Pushdown Automata (NPDAs) are similar to finite automata (FAs), but they contain a stack memory that can hold any amount of data.

Non Deterministic Pushdown Automata

(Source)

Stack in Non-Deterministic Pushdown Automata

The pop action reads the top symbol and removes it from the stack. The push operation pushes a designated symbol to the top of the stack. For example, push(X) means placing X on top of the stack, and the nop operation has no effect.
The stack symbols are distinct from the input tape's "language" alphabet.

Stack is used in the following manner:

  1. In the start state of the control automaton, there are only initial stack symbols on the stack.
  2. The state, input element, and top symbol in the stack determine the next step(transition) at each step.

Steps in Transition

The transition step includes the following:

  1. Make a state change (as FA).
  2. Reading a symbol from the input tape and shifting to the next symbol on the right (as FA).
  3. Modify the stack (add a symbol to the stack, remove a symbol from the stack, or leave the stack alone).

Transition functions formally define transition steps (often in the form of the transition instructions).

Check out this article - Converting NFA to DFA

Formal Definition of NDPAs

Pushdown automaton M is formally defined as a 7-tuple M = (Q, Σ, Γ, T, q0, ⊥, F)
where,

  • Q is the finite set of states
  • is the finite set of input alphabet.
  • q0 ∈ Q  is the initial state
  • F ⊆ Q is the set of final states
  • Γ is the stack alphabet, specifying the set of symbols that can be pushed onto the stack
  • ⊥ is the start stack symbol (⊥ Є  Γ)
  • T is the transition function:

T: Q × ∑ ∪ {∧} × Γ → Γ* × Q

 

Also see, Turing Machine in TOC Arden's theorem

 

You can also read about Greibach Normal Form here.

Frequently Asked Questions

What is meant by regular expression?

A regular expression can also be defined as a pattern sequence that represents a string. It is most commonly used in pattern matching with strings or string matching. 

Write a regular expression for a set of vowels?

The regular expression for a set of vowels is ( a ∪ e ∪ i ∪ o ∪ u ). 

What are Regular Language and Regular Grammar?

Grammar is considered regular if it has rules of the form A -> a or A -> aB or A -> ɛ where ɛ  is a special symbol known as NULL and a language is considered regular if it can be expressed using regular expressions. 

Conclusion

Cheers if you reached here!! 

In this article, we learned about Non-deterministic Pushdown Automata. We also the formal definition of a Non-deterministic Pushdown Automata.

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. Till then, Happy Learning!!

Live masterclass