Jumat, 10 Februari 2012

TEORI BAHASA DAN OUTOMATA


TEORI BAHASA DAN OTOMATA


MATERI KULIAH :
Topik
Substansi
1
Kontrakpembelajaran, Pendahuluan
a.   Ketentuan dalam Kuliah
b.   Pengertian Bahasa
c.   Pengertian Otomata
2
Pengertian Dasar dan Operasi pada string
a. Pngertian Dasar Simbol dll
b. Operasi dasar string
3
Grammar dan Bahasa
a. Definisi Grammar
b. Klasifikasi Grammar/bahasa
c. Penentuan bahasa dari suatu grammar
d.  Penentuan grammar dari suatu bahasa
4,5
Mesin Pengenal Bahasa
(OTOMATA)
a.   Macam-macam mesin pengenal bahasa
b.  Finite State Automata
c.   Ekuivalensi NFA-DFA
6
Ekspresi Reguler.
a.   Pengertian ER
b.   Menentukan ER dari suatu bahasa reguler
c.   Membuat NFA dari ER
7
Ujian sisipan

8,9
Bahasa Bebas Konteks
a. Penyederhanaan tata bahasa bebas konteks
b. Bentuk Normal Chomsky
10,11
PushDown Automata (PDA)
a. Pengertian PDA
b. PDA deterministik/non deterministik.
12
Mesin Turing
a. Pengertian Mesin Turing
b. Penerimaan pada MT
13-15
Topik Khusus
Topik-topik khusus/ masalah2  yang lebih kompleks dari teori bahasa dan otomata.
16
Ujian Akhir





Buku :


  • Teori Bahasa dan Otomata, John E. Hopcroft dkk. (terjemahan, Edisi 2, 2007)
  • Teori Bahasa dan Otomata, Firrar Utdirartatmo
  • Introduction to Languages and The Theory of Computation, John C. Martin
·         An Introduction to Formal Language and Automata, Peter Linz

 

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.

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}.
Diposting oleh di

Tidak ada komentar:

Posting Komentar

Langganan: Posting Komentar (Atom)