31
2.3.2 Hirarki bahasa
menurut
Chomsky
Ada empat jenis bahasa menurut Chomsky, yaitu:
•
Bahasa jenis-0 atau bahasa tak terbatas (unrestricted
language)
Bahasa
jenis-0
dibentuk
dari
tata
bahasa
yang
aturan-aturan produksinya
tidak dibatasi.
•
Bahasa jenis-1 atau bahasa sensitif konteks (context-sensitive
language)
Bahasa
jenis-1
dibentuk
dari
tata
bahasa
yang
aturan-aturan produksinya
berbentuk:
a
?
ß
, |ß| =
|a|.
a, ß ? (N ? T)*
•
Bahasa jenis-2 atau bahasa bebas konteks (context-free language)
Bahasa
jenis-2
dibentuk
dari
tata
bahasa
yang
setiap
produksinya
berbentuk:
A
?
a
A
?
N
a
?
(N ? T)*
•
Bahasa jenis-3 atau bahasa reguler (regular
language)
Bahasa
jenis-3
dibentuk
dari
tata
bahasa
yang
setiap
produksinya
berbentuk:
A
?
a
atau A ? a B
 |