TM as a Language Acceptor
Definition:
Let
M
=
(
Q
,
S
,
G
,
R
,
s
,
F
)
be a
TM
.
The
language accepted by
M
,
L
(
M
)
,
is defined as:
L
(
M
) =
{
w
:
w
Î
S
*
,
s
w
|–
*
x
f
y
;
x
,
y
Î
G
*
,
f
Î
F
}
È
{
e
:
s
D
|–
*
x
f
y
;
x
,
y
Î
G
*
,
f
Î
F
}
M
accepts
w
by a sequence of moves
from
s
to a final state.
Gist:
Illustration:
w
s
x
y
f
•
For
w
¹
e
:
D
D
…
D
D
…
s
x
y
f
•
For
w
=
e
:
D
D
…
D
D
…
15/45