Introduction to PDA | Push Down Automata Definition | TOC | Automata Theory

#pushdownautomata, #PDA, #automata, #TOC
Contact Datils (You can follow me at)
Instagram:   / ahmadshoebk...​  
LinkedIn:   / ahmad-sho...​  
Facebook:   / ahmadshoebkhan​  

Watch Complete Playlists:
Data Structures: https://www.youtube.com/watch?v=jEMmT...
Theory of Computation: https://www.youtube.com/watch?v=p1oqD...
Compiler Design: https://www.youtube.com/watch?v=XMt-K...

Pushdown Automata (Introduction)
Topics Discussed:
1. Introduction to pushdown automata(PDA)
2. Difference between pushdown automata and finite state machine
3. Stack in pushdown automata
4. Push Pop and skip operations in stack
5. Components of pushdown automata
6. DPDA and NPDA

Pushdown automata is simply an NFA augmented with an "external stack memory". The addition of stack is used to provide a last-in-first-out memory management capability to Pushdown automata. Pushdown automata can store an unbounded amount of information on the stack. It can access a limited amount of information on the stack. A PDA can push an element onto the top of the stack and pop off an element from the top of the stack. To read an element into the stack, the top elements must be popped off and are lost.
A PDA is more powerful than FA. Any language which can be acceptable by FA can also be acceptable by PDA. PDA also accepts a class of language which even cannot be accepted by FA. Thus PDA is much more superior to FA.

The PDA can be defined as a collection of 7 components:
Q: the finite set of states
∑: the input set
Γ: a stack symbol which can be pushed and popped from the stack
q0: the initial state
Z: a start symbol which is in Γ.
F: a set of final states
δ: mapping function which is used for moving from current state to next state.
Instantaneous Description (ID)
ID is an informal notation of how a PDA computes an input string and make a decision that string is accepted or rejected.
An instantaneous description is a triple (q, w, α) where:
q describes the current state.
w describes the remaining input.
@ describes the stack contents, top at the left.

pushdown,pushdown automata,pushdown automata tutorial,pushdown automata toc,components of pushdown automata,stack,stack in pushdown automata,push,pop,pushdown automata lectures,toc pushdown automata,toc,toc lectures,automata,automata lectures,theory of computation,theory of computation lectures,automata theory,automata theory lectures,gate lectures,gate toc,toc for gate,gate cs lectures,gate computer science,computer science lectures, pda definition,pushdown automata definition,pushdown automata introduction,introduction to pushdown automata,components of pushdown automata,pda introduction in toc,stack in pushdown automata,push,pop,pushdown automata lectures,toc pushdown ,automata,toc,introduction to pda,definition of pda,automata theory lectures,dpda vs npda,difference between dpda and npda,toc for gate,gate cs lectures,gate computer science,thegatehub,gatehub,pda tuples,tuples in pda