Hardware Reference
In-Depth Information
The next state relation can be extended to have as argument strings in ˙
(i.e.,
Q
Q
iff there exists s
0
2
S such that
˙
S ) as follows: .i; s; s
00
/
S
2
.;s;s
0
/
2
Q
and .i; s
0
;s
00
/
2
. For ease of notation we just use the symbol for
both relations and let the context determine the meaning.
A string x is said to be
accepted
by the FA F if there exists a sequence
of transitions corresponding to x such that there exists a state r
0
2
Q for which
.x; r; r
0
/.The
language
accepted by F , designated L
r
.F /,isthesetof
strings
f
x
j9
r
0
2
QŒ.x;r;r
0
/
g
. The language accepted or
recognized
by s
2
S ,
denoted L
r
.F
j
s/ or L
r
.s/ when F is clear from the context, is the set of strings
f
x
j
.x; r; s/
g
.
If for each present state p and symbol i there is at least one next state n such
that .i;p;n/
2
, the FA is said to be
complete
, otherwise it is
partial
. A partial
automaton can be made complete by directing the unspecified transitions to a non-
accepting state.
An FA is a
deterministic finite automaton
(DFA) if for each present state p and
symbol i there is exactly one next state n such that .i;p;n/
2
.
1
The relation
can be replaced by the next state function ı,definedası
W
˙
S
!
S ,wheren
2
S
is the next state of present state p
2
S on symbol i
2
˙ iff n
D
ı.i; p/.AnFA
that is not a DFA is a
non-deterministic finite automaton
(NDFA).
A string x is said to be
accepted
by the DFA F if ı.x; r/
2
Q.The
language
accepted by F , designated L
r
.F /, is the set of strings
f
x
j
ı.x; r/
2
Q
g
.The
language accepted or
recognized
by s
2
S , denoted L
r
.F
j
s/ or L
r
.s/ when F is
clear from the context, is the set of strings
f
x
j
ı.x; r/
D
s
g
.
The languages associated with finite automata are the regular languages, defined
by means of regular expressions, as established by the theorem due to Kleene [63].
Definition 2.1.3.
The
regular expressions
over an alphabet ˙ are defined recur-
sively as follows:
1.
;
is a regular expression and denotes the empty set.
2. is a regular expression and denotes the set
f
g
.
3. For each a
2
˙ , a is a regular expression and denotes the set
f
a
g
.
4. If l
1
and l
2
are regular expressions denoting the languages L
1
and L
2
, respec-
tively, then .l
1
C
l
2
/, .l
1
l
2
/ and .l
1
/ are regular expressions that denote the sets
L
1
[
L
2
, L
1
L
2
and L
1
, respectively.
The sets denoted by regular expressions are the
regular languages
.
Regular languages are closed under union, concatenation, complementation and
intersection. Also regular languages are closed under projection, lifting and restric-
tion, because they are closed under substitution [63]. Regular languages are closed
under expansion, as shown in Sect.
2.3.1
providing an algorithm that, given the finite
automaton of a language, returns the finite automaton of the expanded language.
1
By the given definition in agreement with standard textbooks (see [63]), a DFA must be a complete
FA, but a complete FA does not need to be deterministic.
Search WWH ::
Custom Search