28
Himpunan
abjad
suatu
bahasa
biasanya
diberi
notasi
S.
Suatu
string
kosong
adalah string
yang tidak mengandung abjad apa pun, dinotasikan sebagai e. Jumlah
simbol-simbol
yang
dipakai
untuk
membentuk
string
s
disebut
panjang
string
s,
dituliskan dengan
notasi |s|. Karena string
e
tidak terdiri dari abjad apa pun,
maka
|e|=0.
Bahasa
yang
terdiri
dari
semua
kemungkinan string
yang
dapat
dibentuk
berdasarkan setiap abjad dalam S disebut bahasa universal dari S, diberi notasi S*.
Sebagai contoh, jika S = { a, o, u } maka S* = { e,
a, o, u, aa,
ao, au, oa, oo, ou, ua,
uo,
uu, aaa,
aao,
… }. Dengan demikian hubungan antara sebuah bahasa L
berdasarkan abjad S dengan bahasa universal dari S adalah L ? S*
2.3.1 Tata
bahasa (grammar)
Biasanya
dalam
literatur-literatur selalu
dipisahkan
definisi
formal
antara
tata
bahasa jenis
yang
satu
dengan
yang
lain.
Karena
definisi
semua
jenis
tata
bahasa
dapat
digeneralisasikan, dalam
skripsi
ini
hanya
akan
dituliskan
satu
definisi
yang
berlaku untuk semuanya.
Suatu
tata bahasa adalah
merupakan 4-tupel G = (N, T, P,
S) (Hopcroft et al.,
1979), dan
bahasa
yang
dibentuk
oleh
G
disebut
bahasa
L(G).
Masing-masing
dijelaskan sebagai berikut.
•
N
adalah himpunan simbol-simbol nonterminal
•
T
adalah himpunan simbol-simbol terminal
•
P
adalah himpunan produksi-produksi atau aturan pengganti, dengan
P
?
(N ?T)* × (N ?T)*
 |