34
2.3.4 Otomata
Otomata dapat digunakan
untuk
mengenali bahasa-bahasa.
Jenis
otomata
yang
akan
dibahas
di
sini
adalah
otomata
berhingga
nondeterministik (nondeterministic
finite
automata
atau
NFA),
otomata
berhingga
deterministik
(deterministic
finite
automata
atau DFA), dan otomata pushdown (pushdown automata
atau PDA).
A. Otomata berhingga deterministik
Otomata
berhingga
deterministik atau
DFA
adalah
5-tupel
(Q,
S,
q
0
,
F,
d),
masing-masing dijelaskan sebagai berikut:
•
Q
adalah himpunan berhingga dari state
•
S
adalah himpunan berhingga abjad-abjad
•
q
0
?
Q
adalah state awal (initial
state)
•
F
?
Q
adalah himpunan state
yang merupakan state akhir (final states)
• d: Q
×
S
?
Q
adalah
fungsi
yang
memetakan pasangan state
dan
abjad
pada state
lainnya, disebut sebagai fungsi transisi.
DFA dapat digunakan untuk mengenali bahasa jenis-3 atau bahasa reguler.
B. Otomata berhingga nondeterministik
Otomata berhingga
nondeterministik atau NFA
adalah 5-tupel (Q,
S, q
0
,
F, ?),
masing-masing dijelaskan sebagai berikut:
•
Q
adalah himpunan berhingga dari state
•
S
adalah himpunan berhingga abjad-abjad
•
q
0
?
Q
adalah state awal (initial
state)
 |