TEORI BAHASA DAN OTOMATA

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 adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

Beberapa Pengertian Dasar :

·   Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah hurufatau 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 lebihsimbol-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 atautanpa 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.  G₁ :  V_T = {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. . G₂ :  V_T = {a}, V = {S}, P = {S ® aS½a} 

S Þ aS

   Þ aaS

   Þ aaa                    L(G₂) ={aⁿ ½ n ≥ 1}

             L(G2)={a, aa, aaa, aaaa,…}