Dasar Teori Bahasa & Grammar

Dasar Teori Bahasa & Grammar •Dasar Teori Bahasa •Grammar & Bahasa •Klasifikasi Noam Chomsky

© B.Very Christioko, S.Kom

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. © B.Very Christioko, S.Kom

Definisi-definisi dalam Teori Bahasa • 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/kosong adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol  (epsilon) sehingga = 0. • Alfabet adalah himpunan hingga (finite set) dari simbol-simbol © B.Very Christioko, S.Kom

Operasi Dasar String (1) 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  adalah semua Prefix(x) • ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbolsimbol paling belakang dari string w tersebut. Contoh : ab, a, dan  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  adalah semua Postfix(x) © B.Very Christioko, S.Kom

Operasi Dasar String (2) Diberikan dua string : x = abc, dan y = 123 • 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 simbolsimbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut. Contoh : abc, ab, bc, a, b, c, dan  adalah semua Substring(x) © B.Very Christioko, S.Kom

Operasi Dasar String (3) Diberikan dua string : x = abc, dan y = 123 • 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  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  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  adalah semua Subsequence(x) © B.Very Christioko, S.Kom

Operasi Dasar String (4) Diberikan dua string : x = abc, dan y = 123 • 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* = xxxxxx… = xx x … • Positive Closure : x = xxxxxx… = xx x … © B.Very Christioko, S.Kom

Konsep Dasar Grammar (1) • 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 ▫ 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 © B.Very Christioko, S.Kom

Konsep Dasar Grammar (2) • Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : , , dan . • Sebuah produksi dilambangkan sebagai   , artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol  dan simbol . • Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai :   . • Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya © B.Very Christioko, S.Kom

Tata Bahasa / Grammar Aturan yang disebutkan pada proses pengenalan dan pembangkitan kalimat. Secara formal, tata bahasa terdiri dari 4 komponen yaitu : 1. Himpunan berhingga, tidak kosong dari simbol-simbol terminal VT 2. Himpunan berhingga, dari simbol-simbol non-terminal VN 3. Simbol awal S ∈ VN, yang merupakan salah satu anggota dari himpunan simbol non-terminal. 4. Himpunan berhingga aturan produksi P yang setiap elemennya dituliskan dalam bentuk :

  dimana α dan β adalah string yang dibentuk dari himpunan VT U VN dan α harus berisi paling sedikit satu simbol nonterminal VN . © B.Very Christioko, S.Kom

Syarat sebuah aturan produksi • Ruas kiri tidak boleh merupakan himpunan kosong (ε, Ǿ). • Contoh : ε  Abd • Ruas kiri harus memuat simbol yang bisa diturunkan (Non Terminal). • Contoh: • A  bd • aB  bd


Grammar • Grammar G didefinisikan sebagai pasangan 4 tuple : VT, VN, S, dan P, dan dituliskan sebagai G(VT, VN , S, P), dimana : • • VT : himpunan simbol-simbol terminal (alfabet) kamus • VN : himpunan simbol-simbol non terminal • S VN : simbol awal (atau simbol start) • P : himpunan produksi


Bahasa yang dihasilkan dari aturan produksi • Bahasa yang dihasilkan oleh G ditulis sebagai L(G), yaitu himpunan string yang dapat diturunkan dari simbol awal S dengan menerapkan aturanaturan produksi yang terdapat pada P (Produksi). • Contoh: Tatabahasa G = {{S} , {a,b}, S , P } dengan aturan produksi P adalah S → aSb S→ε maka dapat dihasilkan suatu string S ⇒ aSb ⇒ aaSbb ⇒aabb sehingga dapat dituliskan S ⇒ * aabb Bahasa yang dihasilkan dari tatabahasa tersebut adalah L(G) = { ε , ab, aabb , aaabbb , aaaabbbb, ... } atau dapat pula dituliskan

L(G )  {a nb n | n  0} © B.Very Christioko, S.Kom

Contoh Grammar: 1. G1 : VT = {I, Love, Miss, You}, VN = {S,A,B,C}, P = {S  ABC, A I, B Love | Miss, C You} S  ABC  IloveYou  IMissYou L(G1)={IloveYou,IMissYou} 2. G2 : VT = {a}, VN = {S}, P = {S  aSa} S  aS  aaS  aaa

L(G2) ={an  n ≥ 1}

L(G2)={a, aa, aaa, aaaa,…} © B.Very Christioko, S.Kom

Klasifikasi Chomsky • Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (  ), Noam Chomsky mengklasifikasikan 4 tipe grammar : 1. Grammar tipe ke-0 : Unrestricted Grammar (UG) Ciri : ,   (VT U VN)*, > 0 2. Grammar tipe ke-1 : Context Sensitive Grammar (CSG) Ciri : ,   (VT U VN) *, 0 <    3. Grammar tipe ke-2 : Context Free Grammar (CFG) Ciri :   VN ,   (VT U VN)* 4. Grammar tipe ke-3 : Regular Grammar (RG) Ciri :   VN ,   {VT, VT VN }


Klasifikasi Chomsky


Unrestricted Grammar (UG) Ciri Utama:  ( V  V ) T N • Ruas kiri anggota dari * • Ruas kanan anggota dari (VT  VN ) • Kardinalitas ruas kiri > 0 • Kardinalitas ruas kanan ≥ 0 • Tidak ada batasan pada aturan produksi Contoh: Abc  De CB  DB Adc  ε © B.Very Christioko, S.Kom

Context Sensitive Grammar (CSG) Ciri Utama: • Panjang ruas kiri ≤ panjang ruas kanan. • Panjang ruas kiri > 0. Contoh: aD  Da AD  aCD AD  abcDE


Context Free Grammar (CFG) Ciri Utama: • Ruas kiri anggota dari VN * ( V  V ) • Ruas kanan anggota dari T N • Ruas kiri tepat satu simbol variabel / Non Terminal Contoh: P  aQb Q abPRS Rε © B.Very Christioko, S.Kom

Regular Grammar (RG) Ciri Utama: • Ruas kiri anggota dari VN • Ruas kanan anggota dari {VT, VT VN } • Ruas kanan berbentuk aB atau a, dengan a Є V*T dan B Є VN • Ruas kiri tepat satu simbol variabel / Non Terminal • Ruas kanan maksimal memiliki sebuah simbol variabel/non terminal yang teletak di paling kanan Contoh: S  aS | aB B bC C  aC | a © B.Very Christioko, S.Kom

Latihan • Buku “Teori Bahasa dan Otomata” Firrar Utdirartatmo, Bab 1 halaman 13.


Dasar Teori Bahasa & Grammar

Recommend Documents