L20 Two way DFA 2 DFA

Lec 20 : Computation Theory Two way DFA (2 DFA)
1
First Example TM
L={0n1n}
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
0\q0 x,R 1\y,L
q0
q1
q2
x\x,R

First Example TM
L={0n1n}
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
0\q0 x,R 1\y,L
q0
q1
q2
x\x,R
B\B,R
q3
q5
0\0,R
y\y,R
y\y,L
y\y,R
0\0,L
x\x,R
0\0,L