35
•
F
?
Q
adalah himpunan state
yang merupakan state akhir (final states)
• d:
Q
× S
?
P(Q)
adalah
fungsi
yang
memetakan
pasangan
state
dan
abjad pada sebuah himpunan state, disebut sebagai fungsi transisi.
NFA
dapat
digunakan untuk
mengenali bahasa
jenis-3
atau
bahasa
reguler.
Dapat dibuktikan bahwa sebuah NFA
memiliki sebuah DFA padanannya (Hopcroft
et
al.,
1979,
pp22-23).
Dengan
demikian
jika
M
N
adalah
sebuah
NFA,
dan
M
D
adalah sebuah DFA, dan R adalah sebuah tata bahasa reguler, maka L(M
N
)
=
L(M
D
)
=
L(R).
C. Otomata pushdown
Otomata
pushdown
atau
PDA
adalah
7-tupel
(Q,
S,
G,
d,
q
0
,
Z
0
,
F),
masing-
masing dijelaskan sebagai berikut:
•
Q
adalah himpunan berhingga dari state
•
S
adalah himpunan berhingga abjad-abjad
•
G
adalah himpunan berhingga simbol-simbol stack
•
q
0
?
Q
adalah state awal (initial
state)
•
Z
0
?
G
adalah simbol awal stack (start
symbol)
•
F
?
Q
adalah himpunan state yang merupakan state akhir (final states)
• d:
Q
×
(S ? {e}) × G ? Q × G*, adalah fungsi transisi
PDA
digunakan untuk
mengenali bahasa
bebas
konteks.
Untuk
tata
bahasa
bebas konteks G terdapat PDA M
P
sedemikian hingga L(M
P
)
=
L(G).
 |