Answer

1. What is Automata?

Automata (plural of Automaton) is an abstract mathematical model of computation. It is a finite representation of an infinite computation that reads input symbols, changes states according to transition rules, and decides acceptance. It is the theoretical foundation for compiler design, lexical analysis, and computability.

Formally, automaton = (Input + Finite Control + Memory + Output/Acceptance).

No physical infinite hardware is needed; the model studies what can be computed with given memory.

2. Classification of Automata

Classification follows memory power and matches Chomsky hierarchy:

A. Finite Automata (FA) — Type-3, Regular

• Memory: Only finite control ($Q$), no auxiliary memory.
• Types: DFA ($\delta: Q\times\Sigma\rightarrow Q$), NFA, $\epsilon$-NFA (all equivalent).
• Power: Regular languages. Example: $L = \{ w \mid \#_0(w) \text{ even}\}$, $(a+b)^*ab$.
• Use: Lexical analyzer, pattern matching.

B. Pushdown Automata (PDA) — Type-2, Context-Free

• Memory: Stack (LIFO). $P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$.
• Types: DPDA vs NPDA (different power).
• Power: CFLs. Example: $L = \{a^n b^n \mid n\ge0\}$, balanced parentheses, arithmetic expressions.
• Use: Syntax analysis (parsing).

C. Linear Bounded Automaton (LBA) — Type-1, Context-Sensitive

• Memory: Tape bounded by input length $|w|$ (plus two endmarkers). Can read/write but not beyond bounds.
• Power: CSLs. Example: $L = \{a^n b^n c^n\}$, $\{a^{n^2}\}$.
• Use: Rare in practice, studies context-sensitive features.

D. Turing Machine (TM) — Type-0, RE

• Memory: Infinite tape, read/write head, finite control.
• Types: Deterministic, Nondeterministic, Multi-tape, Universal (all equivalent in power).
• Power: Recursively Enumerable (Type-0) and Recursive (Decidable) with always-halting variant.
• Example: $L = \{ ww \mid w\in\{a,b\}^*\}$, Halting, any computable function.
• Use: Model of general-purpose computer.

Summary Table

Automaton	Memory	Grammar Type	Language	Decidability
FA (DFA/NFA)	$Q$	Type-3 Regular	Regular	Decidable (all properties)
PDA	$Q$ + Stack	Type-2 CFG	CFL	Emptiness decidable, equivalence undecidable
LBA	$Q$ + tape $|w|$	Type-1 CSG	CSL	Membership decidable ($PSPACE$)
TM	$Q$ + $\infty$ tape	Type-0 unrestricted	RE	Halting undecidable

Hierarchy: $\text{FA} \subset \text{PDA} \subset \text{LBA} \subset \text{TM}$ and $\text{Regular} \subset \text{CFL} \subset \text{CSL} \subset \text{RE}$.

Final Answer

Automata are abstract computing models; classification by memory gives FA → PDA → LBA → TM corresponding to Chomsky Types 3→2→1→0.