To each DFA we associate a language
. To
see whether a word
we put a marker in the initial
state and when reading a symbol forward the marker along the edge
marked with this symbol. When we are in an accepting state at the end
of the word then
, otherwise
.
In the example above we have that
,
and
. Indeed, we have
To be more precise we give a formal definition of . First we
define the extended transition function
. Intuitively,
if starting from
state
we end up in state
when reading the word
. Formally,
is defined by primitive recursion:
As an example we calculate
:
Using
we may now define formally: