- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

A pushdown automaton is used to implement a context-free grammar in the same way that we use a technique to design DFA for a regular grammar. A DFA work on a finite amount of information, where as a PDA works on an infinite amount of information.

Generally, a pushdown automaton is −

"Finite state machine" + "a stack"

A pushdown automaton consist of three components −

an input tape,

a control unit, and

a stack with infinite size.

**Now consider a problem that how to design push down automata for a given language −**

Design a push down automaton which recognizes even length palindromes for **L = {wwR | w ∈ {a, b}+}**.

Read in a string and save it to the stack.

At each step, consider the possibility you might have reached the middle.

Once reaching the midpoint, start working backwards, removing things from the stack if they match what was saved.

At each stop we need to test if we are in the middle of the string.

Step by step instantaneous descriptions for the string **aabbaa** are given below −

Start → (0, aabbaa, $)

Load stack → (0, abbaa, X$)

Load stack → (0, bbaa, XX$)

Load stack → (0, baa, YXX$)

Try, is this the middle? → (1, baa, YXX$)

Pop stack → (1, aa, XX$)

Pop stack → (1, a, X$)

Pop stack → (1, ∧, $)

Done! → (2, ∧, $)

- Related Questions & Answers
- Construct a Turing Machine for language L = {wwr | w ∈ {0, 1}}
- Construct a Turing Machine for language L = {ww | w ∈ {0,1}}
- Construct a TM for the language L= {ww : w ∈ {0,1}}
- Construct a ∈-NFA for the language L = (a* + b*)
- Construct ∈-NFA of Regular Language L = b + ba*
- C program for DFA accepting all strings over w ∈(a,b)* containing “aba” as a substring
- Design NPDA for accepting the language L = {am b(2m) | m>=1}
- Construct a Turing Machine for L = {a^n b^n | n>=1}
- Design a TM which recognizes palindromes over = {a, b}
- Design a TM for equal number of a’s and b’s
- Construct ∈-NFA of Regular Language L = {ab,ba}
- What is a Queue Automaton?
- Construct ∈-NFA of Regular Language L = (00)*1(11)*
- What is Push down automata in TOC?
- Difference b/w getText() and getAttribute() in Selenium WebDriver?

Advertisements