Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

What is a pushdown automaton?

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.

Answers Code

A pushdown automatonPlural: Automata (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's components

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.

%0 node_1 z0 node_1656498398138 a top_node top node_1656498398138->top_node
z0 always remains in the stack and is not be popped

A PDA is a 7-tuple automata (Q,,Γ ,q0,δ,Z0,F )(Q ,∑ ,Γ ,q0 ,δ, Z0, F ). It includes the following:

  • QQ: A set of states
  • : A set of input symbols
  • ΓΓ: A set of the stack elements
  • q0q0: An initial state
  • δδ: A transition function, that is, the condition that allows the state to change
  • Z0Z0: The initial/end stack element
  • FF: A set of final states

Transition notations in PDA

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

g q0 q0 q1 q1 q0->q1 x , z0 /y or ^
A basic notation for a PDA transition

Where xx is the input, Z0Z0 is the top of the stack element. The action we need to take is specified after the "/" sign. The two actions can be as follows:

  • yy is the top two elements of the stack in the case of a push operation
  • ^ specifies to pop, the topmost element of the stack

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 xx is ^.

Turnstile notations

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

IDs include qq, ww, and ss, where:

  • qq is the state
  • ww is the remaining input
  • ss is the stack contents

For example, (q1,ab,aZ0)(q2,b,aaZ0).(q1, ab, aZ0) ⊢ (q2, b, aaZ0).

In this transition, the state changes from q1q1 to q2q2 by consuming the input aa. Also, the input is pushed into the stack.

Examples

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

Palindromes

We can't specify palindromes A palindrome is a word, number, or sentence that reads the same backward and forward. For example, "wow" and "565."with a deterministic finite automaton (DFA) because they require memory. A PDA, however, remembers the elements that must be compared.

Let's suppose L=(SSScS,S=(a,b))L = (SS' | ScS’, S=(a, b)^*), where LL is a palindrome of an even or odd length.

g ENTRY q0 q0 ENTRY->q0 q2 q2 q0->q0 a,a/aa a,b/ab b,a/ba b,b/bb a,z0/a z0 b,z0/b z0 q1 q1 q0->q1 ^,^/^ c,^/^ q1->q2 ^,z0/^ q1->q1 a,a/^ b,b/^

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 cc.

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 Z0Z0, then the string is considered a palindrome.

The or condition

We now look at a slightly complex example.

Let's suppose the following:  L=aibjckij or ik\space L= {a^ib^jc^k | i \neq j \ \mathrm{or} \ i \neq k}

g ENTRY q0 q0 ENTRY->q0 q3 q3 q0->q0 a,z0/az0 a,a/aa q1 q1 q0->q1 ^,a/a q4 q4 q0->q4 ^,a/a q1->q1 b,a/a q2 q2 q1->q2 c,a/^ b,z0/z0 q2->q3 ^,z0/z0 q2->q2 c,z0/z0 c,a/^ ^,a/z0 q4->q4 b,a/a q5 q5 q4->q5 c,a/^ q5->q5 c,a/^ q6 q6 q5->q6 c,z0/z0 ^,a/^ q6->q3 ^,z0/z0 q6->q6 c,z0/z0 ^,a/^

 

As the language contains an or condition, the states change non-deterministically. That is, the q0q0 path changes to the q1q1 path, or the q0q0 path changes to the q4q4 path.

In the path above, the number of aas should not equal the number of bbs.

  • The aas are pushed on the stack one by one, and popped against the bbs.
  • If the stack becomes empty, even though bbs are left in the input or aas remain in the stack, the string is accepted.
  • The ccs are just consumed without any action, as they are irrelevant to these types of strings.

In the path below, the number of aas should not equal the number of ccs.

  • The aas are pushed on the stack one by one, and the bbs are consumed without any action or change to the stack. This is because these are irrelevant to the strings.
  • As the input reaches the ccs, the aas are popped against the ccs. It checks whether the ccs are left in the input, or if the aas 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.

Answers Code
Keep Exploring