PERTEMUAN I

PENDAHULUAN

Teori Bahasa

Teori bahasa membicarakan bahasa formal (formal language),terutama untuk kepentingan perancangan kompilator (compiler) danpemroses naskah (text processor). Bahasa formal adalah kumpulankalimat. Semua kalimat dalam sebuah bahasa dibangkitkan olehsebuah tata bahasa (grammar) yang sama. Sebuah bahasa formalbisa dibangkitkan oleh dua atau lebih tata bahasa berbeda.Dikatakan bahasa formal karena grammar diciptakan mendahuluipembangkitan setiap kalimatnya. Bahasa manusia bersifatsebaliknya; grammar diciptakan untuk meresmikan kata-kata yanghidup di masyarakat. Dalam pembicaraan selanjutnya bahasaformal akan disebut bahasa saja.

Automata

Automata adalah mesin abstrak yang dapat mengenali (recognize),menerima(accept), atau membangkitkan (generate) sebuah kalimat dalam bahasatertentu.Untuk memodelkan hardware dari komputer diperkenalkan otomata.Otomata adalah fungsi-fungsi dari komputer digital. Menerima input,Otomata adalah fungsi-fungsi dari komputer digital. Menerima input,menghasilkan output, bisa memiliki penyimpanan sementara dan mampumembuat keputusan dalam mentransformasikan input ke output. Sebuahbahasa formal adalah suatu abstraksi terdiri dari himpunan simbol-simboldan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinasikanke dalam entitas yang disebut kalimat. Meskipun bahasa formal yangdipelajari di sini lebih sederhana daripada bahasa pemrograman, merekamempunyai banyak hal yan g penting. Kita bisa mempelajari banyaktentang bahasa pemrograman dari bahasa formal.

Otomata merupakan suatu sistem yang terdiri atassejumlah berhingga state, dimana state menyatakaninformasi mengenai input yang lalu dan dapat dianggapsebagai memori mesin. Input pada mesin otomatadianggap sebagai bahasa yang harus dikenali oleh mesin.Selanjutnya, mesin otomata membuat keputusan yangSelanjutnya, mesin otomata membuat keputusan yangmengindikasikan apakah input itu diterima atau tidak.

Beberapa Pengertian Dasar

Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalamgeometri). 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 dibangundari ketiga simbol tersebut.

Jika w adalah sebuah string maka panjang string dinyatakan sebagai | w | dan Jika w adalah sebuah string maka panjang string dinyatakan sebagai | w | dandidefinisikan sebagai cacahan (banyaknya) simbol yang menyusun stringtersebut. Sebagai contoh, jika w = abcb maka | w | = 4.

String hampa adalah sebuah string dengan nol buah simbol. String hampadinyatakan dengan simbol (atau ^) sehingga | |= 0. String hampa dapatdipandang sebagai simbol hampa karena keduanya tersusun dari nol buahsimbol.

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 menghilangkannol atau lebih simbol-simbol paling belakang dari string w tersebut.Contoh : abc, ab, a, dan adalah semua Prefix(x)

ProperPrefix string w adalah string yang dihasilkan dari string w dengan ProperPrefix string w adalah string yang dihasilkan dari string w denganmenghilangkan satu atau lebih simbol-simbol paling belakang dari string wtersebut.Contoh : ab, a, dan adalah semua ProperPrefix(x)

Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w denganmenghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.Contoh : abc, bc, c, dan adalah semua Postfix(x)

ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan daristring w dengan menghilangkan satu atau lebih simbol-simbol paling depan daristring w tersebut.Contoh : bc, c, dan 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 menghilangkansimbol paling depan dari string w tersebut. Contoh : bc adalah Tail(x)simbol paling depan dari string w tersebut. Contoh : bc adalah Tail(x)

Substring string w adalah string yang dihasilkan dari string w denganmenghilangkan 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 adalah semua Substring(x)

ProperSubstring string w adalah string yang dihasilkan dari string w denganmenghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.Contoh : ab, bc, a, b, c, dan adalah semua Substring(x)

Subsequence string w adalah string yang dihasilkan dari string w denganmenghilangkan nol atau lebih simbol-simbol dari string w tersebut.Contoh : abc, ab, bc, ac, a, b, c, dan adalah semua Subsequence(x)

ProperSubsequence string w adalah string yang dihasilkan dari string w denganmenghilangkan satu atau lebih simbol-simbol dari string w tersebut.Contoh : ab, bc, ac, a, b, c, dan adalah semua Subsequence(x)

Concatenation adalah penyambungan dua buah string. Operator concatenationadalah concate atau tanpa lambang apapun.adalah concate atau tanpa lambang apapun.Contoh : concate(xy) = xy = abc123

Alternation adalah pilihan satu di antara dua buah string. Operator alternationadalah alternate atau |.Contoh : alternate(x|y) = x | y = abc atau 123

Kleene Closure : x* = | x | xx xxx | = | x | x 2 | x 3 |

Positive Closure : x + = x | xx | xxx | = x |x 2 | x 3 |

Konsep Dasar1. Dalam pembicaraan grammar, anggota alfabet dinamakan simbol terminal

atau token.2. Kalimat adalah deretan hingga simbol-simbol terminal.3. Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga

kalimat.4. Simbol-simbol berikut adalah simbol terminal (VT) :

huruf kecil alfabet, misalnya : a, b, c simbol operator, misalnya : +, , dan simbol operator, misalnya : +, , dan simbol tanda baca, misalnya : (, ), dan ; string yang tercetak tebal, misalnya : if, then, dan else.

5. Simbol-simbol berikut adalah simbol non terminal (VN) : huruf besar alfabet, misalnya : A, B, C huruf S sebagai simbol awal string yang tercetak miring, misalnya : expr dan stmt.

6. Huruf besar akhir alfabet melambangkan simbol terminal atau non terminal, misalnya : X, Y, Z.

7. Huruf kecil akhir alfabet melambangkan string yang tersusun atas simbol-simbolterminal, misalnya : x, y, z.

8. Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminalatau simbol-simbol non terminal atau campuran keduanya, misalnya : , , dan .

9. Sebuah produksi dilambangkan sebagai , artinya : dalam sebuah derivasidapat dilakukan penggantian simbol dengan simbol .

10. Simbol dalam produksi berbentuk disebut ruas kiri produksi sedangkansimbol disebut ruas kanan produksi.

11. Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuahderivasi dilambangkan sebagai : .

12. Sentensial adalah string yang tersusun atas simbol-simbol terminal atau

12. Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.

13. Kalimat adalah string yang tersusun atas simbol-simbol terminal. Jelaslah bahwakalimat adalah kasus khusus dari sentensial.

14. Pengertian terminal berasal dari kata terminate (berakhir), maksudnya derivasiberakhir jika sentensial yang dihasilkan adalah sebuah kalimat (yang tersusun atas simbol-simbol terminal itu).

15. Pengertian non terminal berasal dari kata not terminate (belum/tidak berakhir),maksudnya derivasi belum/tidak berakhir jika sentensial yang dihasilkanmengandung simbol non terminal.

Grammar dan Klasifikasi Chomsky

Grammar G didefinisikan sebagai pasangan 4 tuple : V T , V N , S, dan Q, dandituliskan sebagai G(V T , V N , S, Q), dimana :VT : himpunan simbol-simbol terminal (atau himpunan token -token, atauhimpunan token -token, atau

alfabet)VN : himpunan simbol-simbol non terminalS V N : simbol awal (atau simbol start)Q : himpunan produksi

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya ( ), NoamChomsky mengklasifikasikan 4 tipe grammar :1. Grammar tipe ke-0 : Unrestricted Grammar (UG)

Ciri : , (V T | VN )*, | | > 02. Grammar tipe ke-1 : Context Sensitive Grammar (CSG)

Ciri : , (V T | VN )*, 0 < | | | | 3. Grammar tipe ke-2 : Context Free Grammar (CFG)

3. Grammar tipe ke-2 : Context Free Grammar (CFG)Ciri : V N , (V T | VN )*

4. Grammar tipe ke-3 : Regular Grammar (RG)Ciri : V N , {V T , V T VN } atau V N , {V T , V N

VT }Mengingat ketentuan simbol-simbol (hal. 3 no. 4 dan 5),

ciri-ciri RG sering dituliskan sebagai : V N , {a, bC} atau V N , {a, Bc}

Contoh Analisa Penentuan Type Grammar1. Grammar G1 dengan Q1 = {S aB, B bB, B b}. Ruas kiri semua

produksinya terdiri dari sebuah V N maka G1 kemungkinan tipe CFG atau RG.Selanjutnya karena semua ruas kanannya terdiri dari sebuah V T atau stringV T VN maka G1 adalah RG.

2. Grammar G 2 dengan Q 2 = {S Ba, B Bb, B b}. Ruas kiri semuaproduksinya terdiri dari sebuah VN maka G 2 kemungkinan tipe CFG atau RG.Selanjutnya karena semua ruas kanannya terdiri dari sebuah V T atau stringV V maka G 2 adalah RG.VN V T maka G 2 adalah RG.

3. Grammar G3 dengan Q 3 = {S Ba, B bB, B b}. Ruas kiri semuaproduksinya terdiri dari sebuah VN maka G 3 kemungkinan tipe CFG atau RG.Selanjutnya karena ruas kanannya mengandung string V T VN (yaitu bB) dan juga string VN V T (Ba) maka G 3 bukan RG, dengan kata lain G 3 adala