- 2073 Chaitra
Compare TM with FA and PDA
Short answer
FA uses finite state memory only, accepts regular languages. PDA adds a stack, accepts context-free languages. TM has infinite tape, read/write, bidirectional; accepts recursively enumerable languages. TM can simulate both; FA ⊂ PDA ⊂ TM. Example: aⁿbⁿ is PDA not FA; aⁿbⁿcⁿ is TM not PDA.
Compare Turing machine with finite automata (FA) and pushdown automata.
| Point | Finite automaton (FA) | Pushdown automaton (PDA) | Turing machine (TM) |
|---|---|---|---|
| Memory | only the current state (finite) | one stack (LIFO) | infinite tape, read and write anywhere |
| Input | read-only, left to right, one pass | read-only, left to right | tape; can read, write, move both ways |
| Head movement | right only | right only (stack top changes) | left, right or stay |
| Languages accepted | regular | context free | recursively enumerable |
| Example | ab | { aⁿbⁿ } | { aⁿbⁿcⁿ }, { ww } |
| Grammar | regular grammar | CFG | unrestricted grammar |
| Determinism | DFA ≡ NFA | DPDA < NPDA | DTM ≡ NTM |
| Halts always? | yes | not necessarily (ε-moves can loop), but membership is decidable | may loop forever |
| Accepts by | final state | final state or empty stack | halting in accepting state |
| Power | weakest | middle | strongest (models any algorithm) |
Summary. FA ⊂ PDA ⊂ TM in power: a TM can simulate a PDA (using part of the tape as a stack) and an FA, but not the reverse. For example, an FA cannot count without bound, so it cannot accept aⁿbⁿ; a PDA can count with its stack but cannot compare three counts (aⁿbⁿcⁿ), since popping destroys the count; a TM can do both by marking symbols on its tape.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Define multitape Turing machine · Theory of Computation, chapter 4
- What is a Turing machine; its operation · Theory of Computation, chapter 4
- How a universal Turing machine works · Theory of Computation, chapter 5
- Multitape TM as copying machine · Theory of Computation, chapter 4
- Regular grammar to RE and FA · Theory of Computation, chapter 2
- TM that doubles a binary number · Theory of Computation, chapter 4
- Differentiate Finite State Machine and Automata · Discrete Structure, chapter 2 · asked 2×
- AI, Turing test, CSP examples · Artificial Intelligence, chapter 1
- Rectangular TM equations; TE10 vs TE20 · RF and Microwave Engineering, chapter 4