Teori Bahasa
- Teori bahasa membicarakan bahasa formal (formal
language), terutama untuk kepentingan perancangan kompilator (compiler)
dan pemroses naskah (text processor).
- Bahasa formal adalah kumpulan kalimat. Semua
kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar)
yang sama.
- Sebuah bahasa formal bisa dibangkitkan oleh dua atau
lebih tata bahasa berbeda.
- Dikatakan bahasa formal karena grammar diciptakan
mendahului pembangkitan setiap kalimatnya.
- Bahasa Natural/manusia bersifat sebaliknya; grammar
diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam
pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.
Otomata (Automata)
·
Otomata adalah mesin
abstrak yang dapat mengenali (recognize), menerima (accept), atau
membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
KONSEP
TEORI BAHASA & OTOMATA
1. Teori Bahasa adalah konsep-konsep pada "string
alpabet“ dalam penyambungan karakter-
karakter alpabet
untuk membentuk suatu makna (bahasa).
2.
Alpabet adalah himpunan simbol (karakter) tidak kosong dan berhingga. Alpabet
digunakan
untuk
membentuk kata-kata (string-string) di bahasa. Bahasa dimulai dengan alpabet.
Alpabet dilambangkan dengan Σ
3.
String adalah deretan simbol dari alpabet dimana perulangan simbol diijinkan.
Contoh
:
V = {a,b,c,d}
String pada alpabet V antara lain ->
'a','abcd','bbba‘
4.
Panjang String adalah jumlah simbol di dalam string bukan pada alpabet dan
pengulangan kemunculan simbol dihitung. Panjang string dilambangkan |w|
Contoh:
|ε|
= 0
|a|
= 1
|aa|
= 2
|aaa|
= 3
|aaab|
= 4
5.
Empty String (null string) adalah string
yang tidak mengandung simbol apapun. Lambangnya e
atau λ
6.
Regular Expression adalah cara untuk mengekspresikan bahasa dengan hanya
menggunakan operasi :
•
Concatenation (Penyambungan)
•
Superscript (Perkalian)
•
Kleene closure (String Tanpa Simbol)
•
Positif closure (Tidak Ada String Kosong Didalamnya)
Concatenation (Penyambungan)
Penyambungan
dilakukan pada 2 karakter atau lebih membentuk 1 barisan karakter (string
simbol).
Contoh
:
'a'
o 'b' = 'ab'
'ab'
o 'baab' = 'abbaab'
Superscript (Perkalian)
Penyambungan dapat dianggap sebagai perkalian karena biasanya
penulisannya adalah bila x dan y string, maka x o y adalah xy. sehingga
pemangkatan dapat digunakan
Contoh : VoV = VV = V2 ----> Panjang string = 2
Kleene closure (String Tanpa Simbol)
adalah string padaV, termasuk string kosong dimana ε string kosong
(string tanpa simbol)
ε mempunyai sifat identitas, yaitu:
ε o x = x
x o ε = x
Positif Closure
(Tidak Ada String Kosong Didalamnya)
V+ = V1 U V2 U V3 U ...
adalah
himpunan string padaV, tidak ada string kosong didalamnya.
V0 = {ε}
adalah
himpunan yang isinya hanya string kosong, dimana String kosong ε tidak sama
dengan himpunan kosong
Beberapa Pengertian Dasar :
·
Simbol adalah sebuah
entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah
huruf atau sebuah angka adalah contoh simbol.
·
String adalah deretan
terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b,
dan c adalah tiga buah simbol maka abcb adalah sebuah string yang
dibangun dari ketiga simbol tersebut.
·
Jika w adalah
sebuah string maka panjang string dinyatakan sebagai ïwï
dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string
tersebut. Sebagai contoh, jika w = abcb maka ïwï=
4.
·
String hampa adalah
sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol e (atau ^) sehingga ïeï= 0. String hampa dapat dipandang sebagai simbol hampa
karena keduanya tersusun dari nol buah simbol.
·
Alfabet adalah
hinpunan hingga (finite set) simbol-simbol
Operasi Dasar String
Diberikan dua string : x = abc, dan y
= 123
·
Prefik string w
adalah string yang dihasilkan dari string w dengan menghilangkan nol atau
lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, a, dan e adalah semua Prefix(x)
·
ProperPrefix string w
adalah string yang dihasilkan dari string w dengan menghilangkan satu
atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : ab, a, dan e adalah semua ProperPrefix(x)
·
Postfix (atau Sufix)
string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling depan dari string w
tersebut.
Contoh : abc, bc, c, dan e adalah semua Postfix(x)
·
ProperPostfix (atau
PoperSufix) string w adalah string yang dihasilkan dari string w
dengan menghilangkan satu atau lebih simbol-simbol paling depan dari
string w tersebut.
Contoh : bc, c, dan e adalah semua ProperPostfix(x)
·
Head string w adalah
simbol paling depan dari string w.
Contoh : a adalah Head(x)
·
Tail string w adalah
string yang dihasilkan dari string w dengan menghilangkan simbol paling
depan dari string w tersebut.
Contoh : bc adalah Tail(x)
·
Substring string w
adalah string yang dihasilkan dari string w dengan menghilangkan nol atau
lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari
string w tersebut.
Contoh : abc, ab, bc, a, b,
c, dan e adalah semua Substring(x)
·
ProperSubstring string
w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling depan dan/atau
simbol-simbol paling belakang dari string w tersebut.
Contoh : ab, bc, a, b, c,
dan e adalah semua Substring(x)
·
Subsequence string w
adalah string yang dihasilkan dari string w dengan menghilangkan nol atau
lebih simbol-simbol dari string w tersebut.
Contoh : abc, ab, bc, ac, a,
b, c, dan e
adalah semua Subsequence(x)
·
ProperSubsequence
string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol dari string w
tersebut.
Contoh : ab, bc, ac, a, b,
c, dan e adalah semua Subsequence(x)
·
Concatenation adalah
penyambungan dua buah string. Operator concatenation adalah concate atau
tanpa lambang apapun.
Contoh : concate(xy) = xy = abc123
·
Alternation adalah
pilihan satu di antara dua buah string. Operator alternation adalah alternate
atau ½.
Contoh : alternate(xy) = x½y = abc atau
123
·
Kleene Closure : x*
= e½x½xx½xxx½…
= e½x½x½x½…
·
Positive Closure : x
= x½xx½xxx½…
= x½x½x½…
Beberapa Sifat Operasi
·
Tidak selalu berlaku :
x = Prefix(x)Postfix(x)
·
Selalu berlaku : x
= Head(x)Tail(x)
·
Tidak selalu berlaku :
Prefix(x) = Postfix(x) atau Prefix(x) ¹ Postfix(x)
·
Selalu berlaku :
ProperPrefix(x) ¹
ProperPostfix(x)
·
Selalu berlaku : Head(x)
¹ Tail(x)
·
Setiap Prefix(x),
ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x),
dan Tail(x) adalah Substring(x), tetapi tidak sebaliknya
·
Setiap Substring(x)
adalah Subsequence(x), tetapi tidak sebaliknya
·
Dua sifat aljabar
concatenation :
·
Operasi concatenation
bersifat asosiatif : x(yz) = (xy)z
·
Elemen identitas
operasi concatenation adalah e
: ex = xe = x
·
Tiga sifat aljabar
alternation :
·
Operasi alternation
bersifat komutatif : x½y = y½x
·
Operasi alternation
bersifat asosiatif : x½(y½z) = (x½y)½z
·
Elemen identitas
operasi alternation adalah dirinya sendiri : x½x = x
·
Sifat distributif
concatenation terhadap alternation : x (y½z) = xy½xz
·
Beberapa kesamaan :
·
Kesamaan ke-1 : (x*)*
= x*
·
Kesamaan ke-2 : e½x = x½e = x*
·
Kesamaan ke-3 : (x½y)* = e½x½y½xx½yy½xy½yx½… = semua string yang merupakan concatenation dari nol atau
lebih x, y, atau keduanya.
GRAMMAR
DAN BAHASA
Konsep
Dasar
·
Anggota alfabet
dinamakan simbol terminal.
·
Kalimat adalah deretan
hingga simbol-simbol terminal.
·
Bahasa adalah himpunan
kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
·
Simbol-simbol berikut
adalah simbol terminal :
·
huruf kecil, misalnya
: a, b, c, 0, 1, ..
·
simbol operator,
misalnya : +, -,
dan ´
·
simbol tanda baca,
misalnya : (, ), dan ;
·
string yang tercetak
tebal, misalnya : if, then, dan else.
·
Simbol-simbol berikut
adalah simbol non terminal /Variabel :
·
huruf besar, misalnya
: A, B, C
·
huruf S sebagai simbol
awal
·
string yang tercetak
miring, misalnya : expr
·
Huruf yunani
melambangkan string yang tersusun atas simbol-simbol terminal atau
simbol-simbol non terminal atau campuran keduanya, misalnya : a, b,
dan g.
·
Sebuah produksi
dilambangkan sebagai a
® b, artinya : dalam sebuah derivasi dapat dilakukan
penggantian simbol a
dengan simbol b.
·
Derivasi adalah proses
pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan
sebagai : a Þ b.
·
Sentensial adalah
string yang tersusun atas simbol-simbol terminal atau simbol-simbol non
terminal atau campuran keduanya.
·
Kalimat adalah string
yang tersusun atas simbol-simbol terminal. Kalimat adalah merupakan sentensial,
sebaliknya belum tentu..
Grammar
Grammar G didefinisikan sebagai pasangan 4 tuple : V, V, S,
dan P, dan dituliskan sebagai G(V,V, S, P),
dimana :
V : himpunan
simbol-simbol terminal (alfabet) àkamus
V : himpunan
simbol-simbol non terminal
SÎV : simbol awal (atau
simbol start)
P :
himpunan produksi
Contoh :
1. G1 : VT = {I,
Love, Miss, You}, V = {S,A,B,C},
P = {S ®
ABC, A® I, B® Love | Miss, C® You}
S Þ
ABC
Þ IloveYou
L(G1)={IloveYou, IMissYou}
2. . G2 : VT = {a}, V = {S}, P
= {S ® aS½a}
S Þ
aS
Þ aaS
Þ aaa
L(G2)
={an ½
n ≥ 1}
L(G2)={a,
aa, aaa, aaaa,…}
Klasifikasi Chomsky
Berdasarkan
komposisi bentuk ruas kiri dan ruas kanan produksinya (a ®
b), Noam Chomsky
mengklasifikasikan 4 tipe grammar :
1.
Grammar tipe ke-0 :
Unrestricted Grammar (UG)
Ciri : a,
b Î (V½V)*,
ïaï> 0
2.
Grammar tipe ke-1 :
Context Sensitive Grammar (CSG)
Ciri : a,
b Î (V½V)
*, 0 < ïaï £
ïbï
3.
Grammar tipe ke-2 :
Context Free Grammar (CFG)
Ciri : a
Î V, b Î
(V½V)*
4.
Grammar tipe ke-3 :
Regular Grammar (RG)
Ciri : a
Î V, b Î
{V, VV} atau a Î V, b
Î {V, VV}
Tipe sebuah grammar (atau bahasa) ditentukan dengan aturan
sebagai berikut :
A language is said to be type-i (i = 0, 1, 2,
3) language if it can be specified by a type-i grammar but can’t be specified
any type-(i+1) grammar.
Contoh
Analisa Penentuan Type Grammar
1.
Grammar G dengan P =
{S ® aB, B ® bB, B ®
b}.
Ruas kiri semua produksinya terdiri dari sebuah V maka G
kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri
dari sebuah V atau string VV maka G adalah RG(3).
2.
Grammar G dengan P =
{S ® Ba, B ® Bb, B ®
b}.
Ruas kiri semua produksinya terdiri dari sebuah V maka G
kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri
dari sebuah V atau string VV maka G adalah RG(3).
3.
Grammar G dengan P =
{S ® Ba, B ® bB, B ®
b}.
Ruas kiri semua produksinya terdiri dari sebuah V maka G
kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung
string VV (yaitu bB) dan juga string VV (Ba) maka G bukan RG, dengan kata lain
G adalah CFG(2).
4.
Grammar G dengan P =
{S ® aAb, B ® aB}.
Ruas kiri semua produksinya terdiri dari sebuah V maka G
kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung
string yang panjangnya lebih dari 2 (yaitu aAb) maka G bukan RG, dengan kata
lain G adalah CFG.
5.
Grammar G dengan P =
{S ® aA, S ® aB, aAb ®
aBCb}.
Ruas kirinya mengandung string yang panjangnya lebih dari 1
(yaitu aAb) maka G kemungkinan tipe CSG atau UG. Selanjutnya karena semua ruas
kirinya lebih pendek atau sama dengan ruas kananya maka G adalah CSG.
6.
Grammar G dengan P =
{aS ® ab, SAc ® bc}.
Ruas kirinya mengandung string yang panjangnya lebih dari 1
maka G kemungkinan tipe CSG atau UG. Selanjutnya karena terdapat ruas kirinya
yang lebih panjang daripada ruas kananya (yaitu SAc) maka G adalah UG.
Derivasi Kalimat dan Penentuan Bahasa
Tentukan bahasa dari masing-masing gramar berikut :
1.
G dengan P = {1. S ® aAa, 2. A ® aAa, 3. A ® b}.
Jawab :
Derivasi kalimat terpendek : Derivasi
kalimat umum :
S Þ
aAa (1) S Þ
aAa (1)
Þ aba (3) Þ aaAaa (2)
¼
Þ aAa (2)
Þ aba (3)
Dari pola kedua kalimat disimpulkan : L(G) = { aba½ n ³
1}
2.
G dengan
P = {1. S ® aS, 2. S ® aB, 3. B ® bC, 4. C ® aC, 5. C ® a}.
Jawab :
Derivasi kalimat terpendek : Derivasi
kalimat umum :
S Þ
aB (2) S Þ
aS (1)
Þ abC (3) ¼
Þ aba (5) Þ aS (1)
Þ aB (2)
Þ abC (3)
Þ abaC (4) ¼
Þ abaC (4)
Þ aba (5)
Dari pola kedua kalimat disimpulkan : L(G)={aba½n ³1,
m³1}
3.
G dengan
P = {1. S ® aSBC, 2. S ® abC, 3. bB ® bb,
4. bC ® bc, 5. CB ® BC, 6. cC ® cc}.
Jawab :
Derivasi kalimat terpendek 1: Derivasi
kalimat terpendek 3 :
S Þ
abC (2) S Þ
aSBC (1)
Þ abc (4) Þ aaSBCBC (1)
Derivasi kalimat terpendek 2 : Þ aaabCBCBC (2)
S Þ
aSBC (1) Þ aaabBCCBC (5)
Þ aabCBC (2) Þ aaabBCBCC (5)
Þ aabBCC (5) aabcBC (4) Þ aaabBBCCC (5)
Þ aabbCC (3) Þ aaabbBCCC (3)
Þ aabbcC (4) Þ aaabbbCCC (3)
Þ aabbcc (6) Þ aaabbbcCC (4)
Þ aaabbbccC (6)
Þ aaabbbccc (6)
Dari pola ketiga kalimat disimpulkan : L (G) = { abc½ n ³
1}
Menentukan Grammar Sebuah Bahasa
1.
Tentukan sebuah gramar
regular untuk bahasa L = { a½
n ³ 1}
Jawab :
P(L) = {S ® aS½a}
2.
Tentukan sebuah gramar
bebas konteks untuk bahasa :
L : himpunan bilangan bulat non negatif ganjil
Jawab :
Langkah kunci : digit terakhir bilangan harus ganjil.
Vt={0,1,2,..9}
Vn ={S, G,J}
P={SàHT|JT|J;
TàGT|JT|J; Hà2|4|6|8; Gà0|2|4|6|8;Jà1|3|5|7|9}
P={SàGS|JS|J;
Gà0|2|4|6|8;Jà1|3|5|7|9}
Buat dua buah himpunan bilangan terpisah : genap (G) dan
ganjil (J)
P(L) = {S ® J½GS½JS, G ® 0½2½4½6½8, J ® 1½3½5½7½9}
3.
Tentukan sebuah gramar
bebas konteks untuk bahasa :
A.
L = himpunan semua
identifier yang sah menurut bahasa pemrograman Pascal dengan batasan : terdiri
dari simbol huruf kecil dan angka, panjang identifier boleh lebih dari 8
karakter
Jawab :
Langkah kunci : karakter pertama identifier harus huruf.
Buat dua himpunan bilangan terpisah : huruf (H) dan angka
(A)
SàHT|H;TàHT|AT|H|A; Hàa|..|z; Aà0|..|9
P(L) = {S ® H½HT,
T ® AT½HT½H½A,
H ®
a½b½c½…,
A ® 0½1½2½…}
4.
Tentukan gramar bebas
konteks untuk bahasa
L(G) = {ab½n,m ³
1, n ¹ m}
Jawab :
Langkah kunci : sulit untuk mendefinisikan L(G) secara
langsung. Jalan keluarnya adalah dengan mengingat bahwa x ¹ y berarti x > y atau x < y.
L = LÈ
L, L ={ab½n
> m ³ 1}, L = {ab½1 £
n < m}.
P(L) = {A ® aA½aC,
C ® aCb½ab}, Q(L) = {B ® Bb½Db,
D® aDb½ab}
P(L) = {S®
A½B, A ® aA½aC,
C ® aCb½ab, B ®
Bb½Db, D® aDb½ab}
5.
Tentukan sebuah gramar
bebas konteks untuk bahasa :
L = bilangan bulat non negatif genap. Jika bilangan
tersebut terdiri dari dua digit atau lebih maka nol tidak boleh muncul sebagai
digit pertama.
Jawab :
Langkah kunci : Digit terakhir bilangan harus genap. Digit
pertama tidak boleh nol. Buat tiga himpunan terpisah : bilangan genap tanpa nol
(G), bilangan genap dengan nol (N), serta bilangan ganjil (J).
P(L) = {S ® N½GA½JA, A ®
N½NA½JA, G®
2½4½6½8,
N®
0½2½4½6½8, J ®
1½3½5½7½9}
Pada state {q0,q1} awalnya belum mempunyai busur dan pada DFA,sebuah state harus mempunyai busur sebanyak himpunan inputnya,karena itu kita tentukan terlebih dahulu arah busurnya dan busurnya ada 2.
δ({q0,q1},0) = {q0,0} ε {q1,0}
= {q0,q1} ε Ø
= {q0,q1}
δ({q0,q1},1) = {q0,1} ε {q1,1}
= {q1} ε {q0,q1}
= {q0,q1}
