Types of Automata

1. Finite Automata (FA)Computers with Finite Memory

2. Push Down Automata (PDA)Infinite Memory (Stack access only)

3. Linear Bounded Automata (LBA)Infinite Memory (List access only)

4. Turing Machines (TM)Infinite Memory (Sequential Tape access)

▲ C O M P L E X I T Y

Hierarchy of Automata

4. Turing Machines (TM)Memory: Infinite Tape (Sequential Access)

3. Linear Bounded Automata (LBA)Memory: Infinite Memory (Restricted List)

2. Push Down Automata (PDA)Memory: Infinite Stack (LIFO Access)

1. Finite Automata (FA)Memory: Finite / Limited States

POWER

TOC