20-07-2012, 12:33 PM
wo-way Deterministic Finite Automata
2way & with output automata.pptx (Size: 151.75 KB / Downloads: 29)
DFA
Input is processed once from left to right. After an input has been read, the DFA decides whether the input is accepted or rejected.
2DFA
Can read the input back and forth with no limit on how many times an input symbol can be read.
As in the case of DFA, the 2DFA decides whether a given input is accepted or rejected.
What is 2DFA?
The concept of 2DFA was originated by Rabin and Scott in 1997
2DFA is a generalized version of the DFA which can revisit characters already processed.
How 2DFA works?
Two-way Finite Automata have a read head, which can move left or right over the input string.
Consists of the symbols of the input string as occupying cells of a finite tape, one symbol per cell.
The input string is enclosed in left and right endmarkers ⊣ and ⊢, which are not elements of the input alphabet Σ.
The read head may not move outside of the endmarkers.
Formal Definition of 2DFA
Is a quintuple
M = ( Q, Σ , δ , q0 , F)
Function δ takes a state and a symbol as arguments and returns a new state and a direction to move the head.
If δ(p, b) = (q, L/R), then whenever the machine is in state p and scanning a tape cell containing symbol b, it moves its head one cell in the direction d and enters state q.
How does DFA compare to 2DFA?
2DFA can solve any problems that are solvable by DFA. Next, are there problems that can be solved by 2DFA but cannot be solved by DFA
Moore and Mealy Machines
Both these machine types follow the basic characteristics of state machines, but differ in the way that outputs are produced.
Moore Machine:
Outputs are independent of the inputs, ie outputs are effectively produced from within the state of the state machine.
Mealy Machine:
Outputs can be determined by the present state and the present inputs, ie outputs are produced as the machine makes a transition from one state to another.