Download Introduction to Computational Linguistics - Uni
Transcript
12. Finite State Automata
38
We extend the notation to regular expressions as follows.
0
(107a)
x −→ y :⇔ false
(107b)
x −→ y :⇔ x = y
(107c)
x −→ y :⇔ x −→ y or x −→ y
(107d)
x −→ y :⇔ exists z: x −→ z and z −→ y
(107e)
x −→ y :⇔ exists n: x −→ y
ε
s∪t
s
t
st
s
s∗
sn
t
In this way, we can say that
(108)
~x
L(A) := {~x ∈ A∗ : there is q ∈ F: i0 −→ q}
and call this the language accepted by A. Now, an automaton is partial if for
a
some q and a there is no q0 such that q → q0 .
Here is part of the listing of the file fstate.ml.
(109)
class automaton =
object
val mutable i = 0
val mutable x = StateSet.empty
val mutable y = StateSet.empty
val mutable z = CharSet.empty
val mutable t = Transitions.empty
method get_initial = i
method get_states = x
method get_astates = y
method get_alph = z
method get_transitions = t
method initialize_alph = z <− CharSet.empty
···
method list_transitions = Transitions.elements t
end;;