Def i ni tion
A 2DFA is an octuple
M
Q
s t r
= ( , , |—, —|, , , , )
Σ
δ
where, Q is a finite set of states
Σ is a finite set of input alphabet.
|— is the left endmarker, |— ∉ Σ ,
—| is the right endmarker, —| ∉ Σ ,
δ :
(
{|—, —|}) (
{ , })
Q
Q L R
× ∪
→
×
Σ
is the tran si tion func tion.
s Q
∈ is the start state,
t Q
∈ is the accept state, and
r Q
∈ is the reject state, r t
≠
such that for all the states q,
δ
δ
( , ) ( , )
,
( ,—| ) ( , )
q t
u R
u Q
q
v L
v Q
=
∈
=
∈
for some
for some
and for all symbols b ∈ ∪
Σ {|—}
δ
δ
δ
δ
( , ) ( , ),
( , ) ( , )
( ,—| ) ( , ),
( ,—| ) ( ,
t b
t R
r b
r R
t
t L
r
r
=
=
=
= L).
δ takes a state and a symbol as arguments and returns a new state and a
direction to move the head i.e., if δ ( , ) ( , ),
p b
q d
=
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 the state q.
1.6 FINITE AUTOMATA WITH OUTPUT
1.6.1 Def i ni tion
A finite-state machine M
Q O
q
= ( , , , , , )
Σ δ λ 0 consists of a finite set Q of
states, a finite input alphabet Σ, a finite output alphabet O, a transition function
δ that assigns to each state and input pair a new state, an output function λ that
assigns to each state and input pair an output, and an initial state q 0 .
Let M
Q O
q
= ( , , , , , )
Σ δ λ 0 be a finite state machine. A state table is used to
denote the values of the transition function δ and the output function λ for all
pairs of states and input.
1.6.2 Mealey Machine
Usually the finite automata have binary output, i.e., they accept the string or do
not accept the string. This is basically decided on the basis of whether the final
state is reached by the initial state. Removing this restriction, we are trying to
consider a model where the outputs can be chosen from some other alphabet.
DFA and NFA
89