10 Difference Between Finite Automata And Turing Machine
Table of Contents
What is a Finite Automata?
Finite Automata(FA) is the simplest machine to recognize patterns. The finite automata or finite state machine is an abstract machine that has five elements or tuples. It has a set of states and rules for moving from one state to another but it depends upon the applied input symbol. Basically, it is an abstract model of a digital computer.
A Finite Automata consists of the following :
Q : Finite set of states. Σ : set of Input Symbols. q : Initial state. F : set of Final States. δ : Transition Function.
What You Need To Know About Finite Automata
- Finite state machines describe the class of regular languages.
- Finite state machines have lower computational power than the Turing machine.
- It consists of finite number of states, finite set of input symbols, initial state of automata and finite set of transition rules for moving from one state to another.
- The input tape is of finite length from both left and right side.
- It recognizes the language called regular language.
- The transition function in finite automata can be represented by :
δ : Q × Σ* → Q - Designing finite automata is easier.
- Head is only able to read the symbols from the tape but cannot write symbols on the tape.
- Head is able to move in right direction only. In two way automata, head is able to move in both directions.
- A finite state machine is just a set of states and transitions. The only memory it has is what state it is in. Thus, the number of memory states is… finite.
What is a Turing Machine?
A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected.
A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −
- Q is a finite set of states
- X is the tape alphabet
- ∑ is the input alphabet
- δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
- q0 is the initial state
- B is the blank symbol
- F is the set of final states
What You Need To Know About Turing Machine
- Turing Machines describe a much larger class of languages, the class of recursively enumerable languages.
- Turing Machines have has more computational power than FSM.
- It also contains finite set of tape symbols and a blank symbol on the tape in addition to finite number of states, finite set of input symbols, initial state of automata and finite set of transition rules for moving from one state to another.
- The input tape is of finite length from left but is of infinite length from right.
- It will recognize not only regular language but also context free language, context sensitive language and recursively enumerable languages.
- The transition function in Turing machine can be represented by : δ : Q × T → Q × T × {L, R} where L and R specifies the left and right movement of tape head.
- Designing Turing machine is difficult and as well as complex.
- Head is able to read as well as write symbols on the tape.
- Head can move in both directions.
- A Turing machine is a finite state machine plus a tape memory. Each transition may be accompanied by an operation on the tape (move, read, write). Its total possible configurations are arbitrarily large, regardless of the size of the program; it expands towards infinity.
Difference Between Finite Automata And Turing Machine In Tabular Form
| BASIS OF COMPARISON | FINITE AUTOMATA | TURING MACHINE |
| Description | Finite state machines describe the class of regular languages. | Turing Machines describe a much larger class of languages, the class of recursively enumerable languages. |
| Computation Power | Finite state machines have lower computational power than the Turing machine. | Turing Machines have has more computational power than FSM. |
| States | It consists of finite number of states, finite set of input symbols, initial state of automata and finite set of transition rules for moving from one state to another. | It also contains finite set of tape symbols and a blank symbol on the tape in addition to finite number of states, finite set of input symbols, initial state of automata and finite set of transition rules for moving from one state to another. |
| Input Length | The input tape is of finite length from both left and right side. | The input tape is of finite length from left but is of infinite length from right. |
| Language Recognition | It recognizes the language called regular language. | It will recognize not only regular language but also context free language, context sensitive language and recursively enumerable languages. |
| Transition Function | The transition function in finite automata can be represented by : δ : Q × Σ* → Q | The transition function in Turing machine can be represented by : δ : Q × T → Q × T × {L, R} where L and R specifies the left and right movement of tape head. |
| Designing | Designing finite automata is easier. | Designing Turing machine is difficult and as well as complex. |
| Head | Head is only able to read the symbols from the tape but cannot write symbols on the tape. | Head is able to read as well as write symbols on the tape. |
| Head Movement | Head is able to move in right direction only. In two way automata, head is able to move in both directions. | Head can move in both directions. |
| Memory | A finite state machine is just a set of states and transitions. The only memory it has is what state it is in. | A Turing machine is a finite state machine plus a tape memory. |
ncG1vNJzZmiumauupbXFn5yrnZ6YsrR6wqikaJyZm7OmvsSnmp5lkprBuLHEp2SfoZ6ewaZ5wK6rqKWRqa5urc2dZK2top67qHnMmpqhoZ6afA%3D%3D