---
title: "Compare TM with FA and PDA"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-compare-fa-pda"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-compare-fa-pda
site: BCT Engineering
---

# Compare TM with FA and PDA

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2073 Chaitra
- Video: [Theory of Automata in 10 Minutes | FA, PDA & Turing Machine Explained with Real Life Example | lec 1](https://www.youtube.com/watch?v=BMIutXDbV-I) — CS With Ahsan 
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-compare-fa-pda
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Compare Turing machine with finite automata (FA) and pushdown automata.

## 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.

## Answer

| 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 | a*b* | { 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which pairing of memory is correct?
   A. FA: stack; PDA: tape; TM: states only
   B. FA: states only; PDA: one stack; TM: infinite tape
   C. FA: tape; PDA: states; TM: stack
   D. All three use a stack
   Answer: B. FA has only finite state, PDA adds a stack, TM has an infinite read/write tape. (Key point: Memory)

2. Which languages do FA, PDA and TM accept respectively?
   A. Regular, context free, recursively enumerable
   B. Context free, regular, RE
   C. Regular, RE, context free
   D. RE, regular, context free
   Answer: A. Power increases FA < PDA < TM. (Key point: Languages)

3. Why can a PDA not accept a^n b^n c^n?
   A. It cannot read c
   B. Popping the stack destroys the count, so it cannot compare three counts
   C. It has no states
   D. It halts early
   Answer: B. One stack can compare two counts but loses the count when popping. (Key point: PDA limit)

4. How does the TM head differ from the FA head?
   A. FA moves left, right or stays; TM only right
   B. FA moves right only; TM moves left, right or stays and can write
   C. Both move right only
   D. Neither can read
   Answer: B. FA reads left to right once; TM can move both ways and rewrite cells. (Key point: Head movement)

## Related in Theory of Computation

- [Define multitape Turing machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-define) — Theory of Computation, chapter 4
- [What is a Turing machine; its operation](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-define-operation) — Theory of Computation, chapter 4
- [How a universal Turing machine works](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Auniversal-tm-example) — Theory of Computation, chapter 5
- [Multitape TM as copying machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-copy) — Theory of Computation, chapter 4
- [Regular grammar to RE and FA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aregular-grammar-to-re-fa) — Theory of Computation, chapter 2
- [TM that doubles a binary number](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-doubles-binary) — Theory of Computation, chapter 4

## Related in other subjects

- [Differentiate Finite State Machine and Automata](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsm-vs-fsa-difference) — Discrete Structure, chapter 2, asked 2×
- [AI, Turing test, CSP examples](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aturing-test-pass-csp-examples) — Artificial Intelligence, chapter 1
- [Rectangular TM equations; TE10 vs TE20](https://www.bctengineer.com/question.md?key=semester_7%2Frf_and_microwave_engineering%3Arectangular-tm-te10-te20) — RF and Microwave Engineering, chapter 4