Trusted answers to developer questions

Zainab Ilyas

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

A **pushdown **** (PDA)** presents a context-free language. A PDA is a finite state machine that has a memory in the form of a stack. We can add elements to the stack to access them for future use.

A PDA consists of three main components:

- An input string or tape
- A finite control unit
- A stack for memory

The stack has two functions: **push** and **pop**. At every step, the PDA makes a decision to push an element from the input, or pop an element from the stack. The stack contains a starting/stopping symbol ($ or Z) that indicates the end of a stack.

z0 always remains in the stack and is not be popped

A PDA is a 7-tuple automata

$Q$ : A set of states$∑$ : A set of input symbols$Γ$ : A set of the stack elements$q0$ : An initial state$δ$ : A transition function, that is, the condition that allows the state to change$Z0$ : The initial/end stack element$F$ : A set of final states

There are several notations to show transitions. The following graph shows one of these transition notations in PDA:

A basic notation for a PDA transition

Where

$y$ is the top two elements of the stack in the case of a*push*- ^ specifies to
*pop*,

Note:It is not necessary to consume the input to move to another state. We can also make a transition non-deterministically (a null transition) where$x$ is ^.

The **turnstile notation** shows a transition without a graph. It uses **instantaneous description (ID) **to do so.

IDs include

$q$ is the state$w$ is the remaining input$s$ is the stack contents

For example,

In this transition, the state changes from

Let's see a few examples to clarify things further:

We can't specify **deterministic finite automaton (DFA)** because they require memory. A PDA, however, remembers the elements that must be compared.

Let's suppose

The PDA above is a non-deterministic PDA that can make a null or epsilon transition. Here, the PDA keeps pushing the elements into the stack.

In the case of an even palindrome, it stops until the first half of the input is consumed. In the case of an odd palindrome, it looks for element

The PDA then compares the input with the stack elements and pops them if it finds a match. At the end of the input, if the stack only contains

`or`

conditionWe now look at a slightly complex example.

Let's suppose the following:

As the language contains an `or`

condition, the states change non-deterministically. That is, the

In the** **path above, the number of

- The
$a$ s are pushed on the stack one by one, and popped against the$b$ s. - If the stack becomes empty, even though
$b$ s are left in the input or$a$ s remain in the stack, the string is accepted. - The
$c$ s are just consumed without any action, as they are irrelevant to these types of strings.

In the path *below*, the number of

- The
$a$ s are pushed on the stack one by one, and the$b$ s are consumed without any action or change to the stack. This is because these are irrelevant to the strings. - As the input reaches the
$c$ s, the$a$ s are popped against the$c$ s. It checks whether the$c$ s are left in the input, or if the$a$ s remain in the stack. If so, the string is accepted.

RELATED TAGS

CONTRIBUTOR

Zainab Ilyas

Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring

Related Courses