23
Nonterminal
biasany a
direp resentasikan
dengan
huruf
besar,
terminal
den gan
huruf
kecil,
dan
simbol
start
den gan
S.
Contohny a
grammar dengan terminal {a,b}, nonterminal {S,A,B}, production rule
S Æ
ABS
S Æ
e
(e adalah string kosong)
BA Æ
AB
BS Æ
b
Bb Æ
bb
Ab Æ
ab
Aa Æ
aa
dan
simbol start S,
menghasilk an language dari semua kata
den gan bentuk
a
n
b
n
(misalny a n jumlah dari a d iikuti oleh n jumlah dari b).
Hirarki Chomsky
terdiri dari beber ap a level b erikut:
•
Grammar tip e-0 (unrestricted grammar)
M
elip uti semua grammar. Ini
menghasilkan semua
language y ang
dap at
diterima
oleh
sebuah
mesin
Turing.
Language
ini
ju ga
diken al
sebagai recursively enumerable languag e.
•
Grammar tip e-1 (context-sensitive grammar)
M
enghasilkan context-sensitive
language. Grammar ini
memiliki
aturan
dari
bentuk
aAß
Æ
a?ß
dengan
A
sebagai
nonterminal,
sementara a, ß, dan ? seb agai
string termin al d an nontermin al. S tring a,
ß
dap at bernilai kosong,
sedan gk an ?
tidak
dap at
bernilai kosong.
Aturan
S
Æ e
diijinkan
jika
S
tidak
muncul
di
sisi
kanan
dari
aturan
ap ap un.
 |