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
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}.
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 :
B. 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}
C. Mesin Pengenal Bahasa
Untuk setiap kelas bahasa Chomsky, terdapat sebuah mesin pengenal bahasa. Masing-masing mesin tersebut adalah :| Kelas Bahasa | Mesin Pengenal Bahasa |
| Unrestricted Grammar (UG) | Mesin Turing (Turing Machine), TM |
| Context Sensitive Grammar (CSG) | Linear Bounded Automata, LBA |
| Context Free Gammar (CFG) | Pushdown Automata, PDA |
| Regular Grammar, RG | Finite State Automata, FSA |
· FSA didefinisikan sebagai pasangan 5 tupel : (Q, ∑, δ, S, F).
Q : himpunan hingga state
∑ : himpunan hingga simbol input (alfabet)δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.
Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
S Î Q : state AWAL
F Ì Q : himpunan state AKHIR
Contoh : FSA untuk mengecek parity ganjil
Q ={Gnp, Gjl} diagram transisi
tabel transisi
| δ | 0 | 1 |
| Gnp | Gnp | Gjl |
| Gjl | Gjl | Gnp |
· Ada dua jenis FSA :
· Deterministic finite automata (DFA)
· Non deterministik finite automata.(NFA)
- DFA : transisi state FSA akibat pembacaan sebuah simbol bersifat tertentu.
δ : Q ´ ∑® Q
- NFA : transisi state FSA akibat pembacaan sebuah simbol bersifat tak tentu.δ : Q ´ ∑ ® 2Q
DFA :
Q = {q0, q1, q2}
δ diberikan dalam tabel berikut :
| ∑= {a, b} | δ | a | b |
| S = q0 | q0 | q0 | q1 |
| F = {q0, q1} | q1 | q0 | q2 |
| q2 | q2 | q2 |
a b a
a b
Kalimat yang diterima oleh DFA : a, b, aa, ab, ba, aba, bab, abab, baba
Kalimat yang dittolak oleh DFA : bb, abb, abba
DFA ini menerima semua kalimat yang tersusun dari simbol a dan b yang tidak mengandung substring bb.
Contoh :
Telusurilah, apakah kalimat-kalimat berikut diterima DFA di atas :
abababaa è diterima
aaaabab è diterima
aaabbaba è ditolak
Jawab :
i) δ (q0,abababaa) Þ δ (q0,bababaa) Þ δ (q1,ababaa) Þ
δ (q0,babaa) Þ δ (q1,abaa) Þ δ (q0,baa) Þ δ (q1,aa) Þ
δ (q0,a) Þ q0
Tracing berakhir di q0 (state AKHIR) Þ kalimat abababaa diterima
ii) δ (q0, aaaabab) Þδ (q0,aaabab) Þδ (q0,aabab) Þ
δ (q0,abab) Þ δ (q0,bab) Þ δ (q1,ab) Þ δ (q0,b) Þ q1
Tracing berakhir di q1 (state AKHIR) Þ kalimat aaaababa diterima
iii) δ (q0, aaabbaba) Þ δ (q0, aabbaba) Þ δ (q0, abbaba) Þδ (q0, bbaba) Þ δ (q1,baba) Þ δ (q2,aba) Þ δ (q2,ba) Þ δ (q2,a) Þq2
Tracing berakhir di q2 (bukan state AKHIR) Þ kalimat aaabbaba ditolak
Kesimpulan :sebuah kalimat diterima oleh DFA di atas jika tracingnya berakhir di salah satu state AKHIR.
NFA :
Berikut ini sebuah contoh NFA (Q, ∑, δ, S, F). dimana :
Q = {q, q, q,q, q} δ diberikan dalam tabel berikut :
| ∑= {a, b,c} | δ | a | b | c |
| S = q | q | {q, q} | {q, q} | {q, q} |
| F = {q} | q | {q, q} | {q} | {q} |
| q | {q} | {q, q} | {q} | |
| q | {q} | {q} | {q, q} | |
| q | Æ | Æ | Æ |
a, b, c a, b, c
a
q q
c b a
b
q q q
a, b, c a, b, c
c
kalimat yang diterima NFA di atas : aa, bb, cc, aaa, abb, bcc, cbb
kalimat yang tidak diterima NFA di atas : a, b, c, ab, ba, ac, bc
Sebuah kalimat di terima NFA jika :
· salah satu tracing-nya berakhir di state AKHIR, atau
· himpunan state setelah membaca string tersebut mengandung state AKHIR
Contoh :
Telusurilah, apakah kalimat-kalimat berikut diterima NFA di atas :
ab, abc, aabc, aabb
Jawab :
1. δ(q,ab) Þ δ(q,b) È δ(q ,b) Þ {q, q} È {q} = {q, q, q}
Himpunan state TIDAK mengandung state AKHIR Þ kalimat ab tidak diterima
2. δ(q,abc) Þ δ(q,bc) È δ(q ,bc) Þ { δ(q,c) È δ(q,c)}Èδ(q, c){{ q, q}È{ q}}È{ q} = {q, q, q,q}
Himpunan state TIDAK mengandung state AKHIR Þ kalimat abc tidak diterima
3. δ(q,aabc) Þ δ(q,abc) È δ(q ,abc)Þ{ δ(q,bc) È δ(q ,bc)} È
δ (q ,bc) Þ{{ δ(q, c) È δ(q,c)} È δ(q, c)} È δ(q, c) Þ
{{{ q, q}È { q}} È {q}} È {q} = {q, q, q,q}
Himpunan state TIDAK mengandung state AKHIR Þ kalimat aabc tidak diterima
4. δ(q,aabb) Þ δ(q,abb) È δ(q ,abb)
Þ { δ(q,bb) È δ(q ,bb)} È δ (q ,bb)
Þ{{ δ(q, b) È δ(q,b)} È δ(q, b)} È δ(q, b)
Þ{{{ q, q}È { q, q}} È {q}} È {q} = {q, q, q, q}
Himpunan state mengandung state AKHIR Þ kalimat aabb diterima
Bermanfaat buat tugas saya gan
ReplyDelete