Two - Way Finite Automata

Two - Way Finite Automata

Described by 5 - tuples ( Q , Σ , δ , q₀ , F ), where

• Q is a finite set of states(denoted by capital letters like A, B... etc).
• Σ is a finite set of input terminals (Denoted by small letters like a, b... etc).
• δ is the transition function, that is, δ: Q X Σ → Q X { L, R }
• q₀ is the initial state.
• F is a set of final state

Transition Table : 

States	0	1
-> q0	( q0, R )	( q1, R )
q1 (Final State)	( q1, R )	( q2, L )
q2	( q0, R )	( q2, L )

To understand the concept of  two - way FA and, Let us take an example.

Example : 

Consider the transition table .check the string " 101001 " whether it is accepted by Two - Way DFA or not? 

States	0	1
-> q0	( q0, R )	( q1, R )
q1 (Final State)	( q1, R )	( q2, L )
q2	( q0, R )	( q2, L )

Acceptability of the string using Two - way DFA is -

Here we started from the initial state q0 and finally reached to q1 (final state). so the string "101001" is accepted by Two - Way DFA.

Conversion from Two - Way DFA (2-DFA) to NFA 

• To convert the 2-DFA into NFA, first of all we have to find out the crossing sequence.
• The list of states below each boundary between squares is termed as crossing sequence.
• For making the table of NFA, we have to find out the left match or right match of the states.

Crossing Sequence for the string "101001" of the above example is -

  

Right Match examples of the above crossing sequence-

here {q1} is the right match of {q0} at input "1"

here {q1 q2 q0} is the right match of {q1} at input "0"

Using with the help of above two diagrams for the right match, we make the NFA table. similarly we can make the NFA table using left match.

NFA table is -

States	Right match 0	Right match 1
->[q0]	-	[q1]
[q1] (Final State)	[q1 q2 q0][q1]	-
[q1 q2 q0]	-	[q1]

here there is not any right match of q0 at input"0" but at input "1", right match is q1.

for q1, right match at input "0" is [q1 q2 q0] and [q1] because we check q1 at two places in the crossing sequence diagram and there is not any right match at input "1".