Introduction to Pushdown Automata

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} 

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

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

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 article, we talked about pushdown automata (PDA), a computational model that recognizes context-free languages. We discussed its components, including the input tape, stack, states, transition function, and acceptance condition, which together enable the PDA to process input strings and determine their validity based on a given context-free grammar.

Recommended Readings:

• Basics of TOC
• Deterministic Finite Automata
• Non Deterministic Finite Automata
• Finite State Machine
• Context-Free Grammar and Language
• Automata Theory

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 Code 360.

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 Code 360