- Moore & Mealy Machines
- DFA Minimization
- NDFA to DFA Conversion
- Non-deterministic Finite Automaton
- Deterministic Finite Automaton
- Automata Theory Introduction
- Automata Theory - Home
Classification of Grammars
Regular Grammar
- DFA Complement
- Pumping Lemma for Regular Grammar
- Constructing FA from RE
- Regular Sets
- Regular Expressions
Context-Free Grammars
- Pumping Lemma for CFG
- Greibach Normal Form
- Chomsky Normal Form
- CFG Simplification
- CFL Closure Properties
- Ambiguity in Grammar
- Context-Free Grammar Introduction
Pushdown Automata
- PDA & Parsing
- PDA & Context Free Grammar
- Pushdown Automata Acceptance
- Pushdown Automata Introduction
Turing Machine
- Linear Bounded Automata
- Semi-Infinite Tape Turing Machine
- Non-Deterministic Turing Machine
- Multi-Track Turing Machine
- Multi-tape Turing Machine
- Accepted & Decided Language
- Turing Machine Introduction
Decidability
- Post Correspondence Problem
- Rice Theorem
- Turing Machine Halting Problem
- Undecidable Language
- Language Decidability
Automata Theory Useful Resources
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
Multi-tape Turing Machine
Multi-tape Turing Machines have multiple tapes where each tape is accessed with a separate head. Each head can move independently of the other heads. Initially the input is on tape 1 and others are blank. At first, the first tape is occupied by the input and the other tapes are kept blank. Next, the machine reads consecutive symbols under its heads and the TM prints a symbol on each tape and moves its heads.
![Multi-tape Turing Machine](/automata_theory/images/multi_tape_turing_machine.jpg)
A Multi-tape Turing machine can be formally described as a 6-tuple (Q, X, B, δ, q0, F) where −
Q is a finite set of states
X is the tape alphabet
B is the blank symbol
δ is a relation on states and symbols where
δ: Q × Xk → Q × (X × {Left_shift, Right_shift, No_shift })k
where there is k number of tapes
q0 is the initial state
F is the set of final states
Note − Every Multi-tape Turing machine has an equivalent single-tape Turing machine.
Advertisements