TM

Turing Machines: (TM)
Turing machine is a simple mathematical model of a computer. Turning machine models the computing capability of a general- purpose computer. This model will enable us not only to study some theoretical limitations on the tasks that computers can perform, it will also be a model that we can use to show that certain operations "can" be done by computer.
The languages accepted by F.A. are called "regular" and they can be defined by regular expression. The languages accepted by PDA are called CFGs. The languages accepted by TM are called type ?, or phrase-structure or recursively enumerable language.
Turing Machines: (TM)
Turing machine is a simple mathematical model of a computer. Turning machine models the computing capability of a general- purpose computer. This model will enable us not only to study some theoretical limitations on the tasks that computers can perform, it will also be a model that we can use to show that certain operations "can" be done by computer.
The languages accepted by F.A. are called "regular" and they can be defined by regular expression. The languages accepted by PDA are called CFGs. The languages accepted by TM are called type ?, or phrase-structure or recursively enumerable language.


Two way DFA (2 DFA)
In comparison, DFA and 2DFA differ in that an input can be read only once from left to right by a DFA, whereas A 2DFA can read the input back and front with no limit on how many times an input symbol can be read.
Definition A 2DFA over ? is a system A=(Q,?,q0,F) as in DFA with the difference that now ? is a function from
Q×? into Q×D where D={L,R,S}
Example:
Design A 2DFA that accept “101” and go back to the beginning of the tape