Pushdown Automata

Pushdown Automata

A Pushdown automata (PDA) works similar as DFA.

A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.

A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q0, I, F) −

1. Q: Finite number of states
2. ∑: Input alphabet
3. S: Stack
4. δ: Transition function: Q × (∑ ∪ {ε}) × S × Q × S*
5. q0: Initial state (q0 ∈ Q)
6. I: Initial stack top symbol (I ∈ S)
7. F: Final state

PDA = FSM + Stack

Where, FSM for finite state machine.

Components of PDA are,

1. Input tape
2. Control unit
3. Stack

---

Related topics :

1. Definition of DFA
2. DFA notations
3. How DFA process inputs
4. DFA solved examples
5. Minimization of DFA
6. Definition of NFA
7. Equivalent of DFA and NFA
8. Properties of transition functions
9. Trape/ Dead state
10. Moore machine
11. Mealy machine
12. Mealy to Moore machine conversion
13. Moore to Mealy machine conversion
14. Difference between Mealy and Moore machine
15. Regular expression
16. Regular expression examples
17. Regular expresstion to CFG
18. Regular expression to Regular grammar
19. Ambiguous grammar
20. Leftmost and Rightmost derivations
21. Arden's Law
22. NFA with ∈ moves
23. Construct NFA without ∈ moves
24. NFA with ∈ to DFA Indirect method
25. Context Free Grammars
26. Convert CFG in to CNF
27. CFL are not closed under intersection