Two way DFA (2 DFA)

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





























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.


…
…
B B …

The figure above is basic Turing machine, has a finite control, an input tape that is divided into cells, and a tape head that scan one cell of the tape at a time. The tape has a leftmost cell bat is infinite to the right. Each cell of the tape may hold exactly one symbol. Initially, the n leftmost cells hold the input. The remaining infinity of cells each hold the blank.
In one move the Turing machine, depending upon the symbol scanned by the tape head and the state of the finite control,
1- changes state,
2- prints a symbol on the tape cell scanned, replacing what was written there, and
3- moves its head left or right one cell
Note that the difference between a Turing machine and a two-way finite automation lies in the ability to change symbols on its tape.
Formally, a Turing machine (TM) is denoted:

Where
Q is the finite set of "states",
is the finite set of a allowable "tape symbols",
B, a symbol of , is the "blank",
, a subset of not including B, is the set of "input symbols"
T, is the next move function, a mapping from to ,
, in Q is the "start state ",
is the set of "final states", or called "HALT states" that cause execution to terminate when we enter them.
The "language accepted" by M, denoted L(M), is the set of those word in that cause M to enter a final state.





























and Transition functions are:






A computation of M on input is: