12 0 2 MB
TEORI BAHASA DAN AUTOMATA
DR. BUDI NURWAHYU., M.SI
DAFTAR ISI A. Bahasa Formal ................................................................. 2 B. Defini Rekursi ............................................................... 11 C. Ekspresi Reguler .......................................................... 17 D. Automata ....................................................................... 19 E. Teori Kleene .................................................................. 26 F. Automata Beroutput .................................................. 41
Teori Bahasa dan Automata | 1
BAHASA FORMAL A. Bahasa Formal Bahasa terbagi dua: 1. Bahasa Semantik Bahasa yang dimengerti karena tahu artinya. Umumnya
bahasa
tingkat
tinggi
dan
digunakan oleh manusia. 2. Bahasa Formal Bahasa yang dimengerti karena tahu bentuk katanya. Umumnya digunakan oleh mesin.
B. Definisi 1. Abjad/karakter Unsur terkecil dalam bahasa formal. Contoh : a,b,c,d..., -, +, =, ?, !, dll. 2. Alfabet Kumpulan abjad/karakter yang disimbolkan dalam bentuk ∑. Contoh :
Teori Bahasa dan Automata | 2
∑ = {a, b, c, d ..., z} ∑ = {0, 1} 3. String Deretan atau susunan abjad. Contoh : ∑ = {a, b, c} String-stringnya adalah ab, ac, acb... 4. String Kosong String
yang
tidak
memuat
abjad.
Dilambangkan dengan Ԑ (dibaca: epsilon). 5. Panjang String Banyaknya abjad yang ada didalam S. Dilambangkan dengan |S|. Contoh : |ab| = 2 |aaabbc| = 6 |Ԑ| = 0 6. Operasi Konkatenasi Konkatenasi antara string S dengan string T menyambungkan S dengan T menjadi S˳T.
Teori Bahasa dan Automata | 3
Contoh 1: S = abab T = bcaab S˳T = ababbcaab
Makassar, 2017
25
Oktober
Akibatnya panjang dari S dan T ditambah S˳T : |S˳T|= |S|+|T|= 4+5=9 S˳Ԑ=S, Ԑ˳S=S, Ԑ˳Ԑ=Ԑ S˳S˳S=S3 Contoh 2: S= ba S3=bababa 7. Balikan String (invers string) Balikan dari string S adalah suatu string yang diperoleh dari membaca S secara terbalik. Dilambangkan dengan S-1. Contoh : S= abaac S-1 = caaba Sifat balikan string a) |S-1|= |S| Contoh :
Teori Bahasa dan Automata | 4
S= abaac |S|= 5 b) (S˳T)-1 = T-1˳S-1Contoh : S= baa T= acba S-1= aab
T-1= abca
S˳T= (baa)˳(acba)= baaacba (S˳T)-1= abcaaab T-1˳S-1= (abca)˳(aab) = abcaaab 8. String Palindrom S disebut string Palindrom jika S-1= S. Contoh: S= abba S-1= abba 9. Bahasa Formal Dari alfabet zigma (∑) adalah kumpulan string yang dapat dibuat dari abjad dalam ∑, melalui operasi konkatenasi. Lambang bahasa = L. Contoh : ∑= {a,b} L= {a,ba,bb,aab,baab}
Teori Bahasa dan Automata | 5
L= {aaba,bbb,baab,abaab} Misalkan: Ln-1 adalah bahasa yang setiap stringnya mempunyai panjang n. L1= {a,b} mempunyai 2 string L2= {aa,bb,ba,bb} 4= 22 string (4 string) L3= {aaa,aab,aba,baa,abb,bab,bba,bbb}
8= 23 string Secara umum Ln akan memuat 2n string.
C. Bahasa Palindrom L disebut bahasa palindrom, jika setiap string didalam L adalah string palindrom. Contoh : ∑= {a,b} L= {a,aba,bab,bbb,baab) L adalah palindrom Misalkan Pn adalah bahasa palindrom yang panjang setiap stringnya adalah n.
Teori Bahasa dan Automata | 6
P1= {a,b} P2= {aa,bb}
Banyaknya string P1 sama banyaknya string P2 yaitu 2. P3= {aaa,bbb,bab,aba} P4= {aaaa,bbbb,baab,abba}
Banyaknya string P3 sama banyaknya string P4
-
yaitu 22, maka akan diperoleh : Banyaknya string P5= banyaknya string P6= 8=23 Banyaknya string P7= banyaknya string P8= 16=24 Secara umum: Banyaknya string P2n-1= banyaknya string P2n=2n. Dimana n= 1,2,3,4,... dst
D. Klosur Misalkan S adalah kumpulan string. Klosur dari S ditulis S˟, adalah kumpulan semua string
–
string
dalam
S
melalui
operasi
Teori Bahasa dan Automata | 7
konkatenasi. Jika S˟ adalah klosur dari S, maka string kosong Ԑ ada didalam S˟. Contoh: S= {a} Maka S˟= {Ԑ,a,aa,aaa,aaaa,aaaaa,aaaaaa....} Jika S= {a} maka S˟ dapat ditulis sebagai a˟. a˟= {Ԑ,a,aa,aaa,aaaa,aaaaa,aaaaaa....} a˟ adalah bahasa yang setiap stringnya dibangun oleh a. Contoh: S= {a,b} S˟= {Ԑ,a,b,aa,ab,ba,bb,aaa,aab,aba,baa,abb,bab,bba ,bbb...} Jika S= {a,b} maka S˟ dapat Tentukan bahasa reguler dari ∑= {a,b} yang setiap stringnya memuat 2ˈbˈ. ditulis sebagai (a+b)˟.
Teori Bahasa dan Automata | 8
(a+b)˟= {Ԑ,a,b,aa,ab,ba,bb,aaa...} adalah bahasa yang memuat semua string yang dapat dibuat dari ˈaˈ atau ˈbˈ. a˟¸ba˟= {Ԑ,a,aa,aaa...}¸b¸{Ԑ,a,aa,aaa...} = {b,ab,ba,aba,aab,baa,abaa,...} string – string yang memuat
Karnasatu setiap ˈbˈ didalam a˟¸ba˟ adalah string yang memuat satu b1 maka a˟¸ba˟ disebut bahasa yang setiap stringnya memuat satu b1. a˟¸ba˟ disebut bahasa reguler.
Cara
menentukan
bahasa
reguler
dapat
menggunakan pola string. Contoh : Cara pola string sebagai berikut: 1. Memuat 1ˈbˈ b
a˟.b.a˟
string – string yang dibuat dari ˈaˈ a˟
2. Memuat 2ˈbˈ b
b
string – string yang dibuat dari ˈaˈ a˟
Maka bahasa regulernya adalah a˟ba˟ba˟ Contoh :
Teori Bahasa dan Automata | 9
∑ {a,b} Tentukan bahasa reguler yang setiap stringnya berakhir ˈbˈ. Jawab: b semua string yang dapat dibuat dari ˈaˈ atau ˈbˈ (a+b)˟
Bahasa reguler yang setiap stringnya berakhir b adalah (a+b)˟b. Contoh: Buatlah bahasa reguler yang setiap stringnya berakhir ˈbˈ atau yang memuat 1ˈaˈ. Jawab : Karena ada kata “atau” berarti ada 1 pola string yang harus digabung pada string 1 (string yang berakhir ˈbˈ). a) Pola string 1 (string yang berakhir ˈbˈ) a˟ ba˟ sembarang string dibuat dari ˈaˈ atau ˈbˈ (a+b)˟
Teori Bahasa dan Automata | 10
b) Pola string 2 (string yang memuat 1 ˈaˈ)
a sembarang string dibuat dari ˈbˈ b˟ Maka bahasa regulernya b˟¸a¸b˟
Bahasa reguler yang setiap stringnya berakhir ˈbˈatau memuat 1ˈaˈ adalah: (a+b)˟.b+b˟.a.b˟
Latihan Buatlah bahasa reguler yang setiap stringnya memuat paling sedikit 1ˈbˈ.
Teori Bahasa dan Automata | 11
DEFINISI REKURSI A. Rekursi Rekursi adalah proses yang sama dilakukan berulang – ulang untuk memperoleh hasil yang lebih baik. Bahasa
reguler
pada
umumnya
dapat
diperoleh melalui proses rekursi.
Teori Bahasa dan Automata | 12
Contoh : ∑= {a,b} L adalah bahasa yang setiap stringnya berakhir ˈbˈ. Buatlah proses rekursi untuk L. Jawab : L1= L= {b} L2= Jika χL maka aχL dan bχL. Ulangi L2 Hasil rekursi L adalah L1= L= {b} L2= karna bL abL dan bbL L= {b,ab,bb}. Ulangi L2 L2= karna abL aabL dan babL. Karna bbL abbL dan bbbL L= {b,ab,bb,aab,bab,abb} Karna hasil rekursi L sama dengan bahasa reguler L maka definisi rekursi dari L sudah benar.
B. Contoh Definisi Rekursi
Makassar, 1 November 2017
Teori Bahasa dan Automata | 13
Contoh 1: ∑= {a,b} L adalah bahasa yang setiap stringnya berawal ˈbˈ. Buatlah definisi rekursi dari bahasa L tersebut. Jawab : L adalah bahasa yang setiap stringnya berawal ˈbˈ. L= {b,ba,bb,baa,bab,bba,bbb,baaa,...} Jadi ˈbˈ adalah string terpendek dalam L. maka langkah awal definisi rekursi adalah L={b}. Dan langkah berikutnya, jika χL maka χaL dan χbL Jadi definisi rekursi dari bahasa L adalah : Langkah 1 : L= {b} Langkah 2 : Jika χL maka χaL dan χbL ulangi langkah 2. Simulasi dari hasil definisi rekursi tersebut. Langkah 1 : L= {b}. Langkah 2 : Karna bL maka baL dan bbL. Jadi L= {b,ba,bb} ulangi langkah 2.
Teori Bahasa dan Automata | 14
Karna baL maka baaL dan babL. karna bbL maka bbaL dan bbbL. Jadi L={b,ba,bb,baa,bab,,bba,bbb} Jika proses tersebut diulang – ulang maka akan diperoleh bahasa L yang setiap stringnya berawal ˈbˈ. Jadi definisi rekursi diatas sudah benar.
Contoh 2: ∑= {a,b} L adalah bahasa yang setiap stringnya berakhir ˈbˈ. Buatlah definisi rekursi dari bahasa L tersebut. Jawab : Langkah 1 : L= {b} Langkah 2 : Jika χL, maka χaL dan χbL. Simulasi dari hasil definisi rekursi tersebut. Langkah 1 : L= {b} Langkah 2 : Karna abL dan bbL. Maka L= {b,ab,bb}. Ulangi langkah 2.
Teori Bahasa dan Automata | 15
Karna abL aabL dan babL. Karna bbL abbL dan bbbL. Maka L= {b,ab,bb,abb,bab,abb,bbb} Jadi jika langkah 2 diulangi terus menerus maka akan diperoleh bahasa L adalah bahasa yang setiap stringnya berakhir ˈbˈ. Contoh 3: ∑= {a,b} L adalah bahasa yang setiap stringnya berawal ˈbˈ berakhir ˈaˈ . Buatlah definisi rekursi dari bahasa L tersebut. Jawab : L= {ba,baa,bba,baaa,baba,bbaa,bbba,...} Misal L1= {b,ba,bb,baa,bab,bba,bbb,...} stringnya berawal ˈbˈ
L1a = {ba,baa,bba,baaa,baba,bbaa,bbba,...} Stringnya berawal ˈbˈ berakhir ˈaˈ Defini Rekursi
Langkah 1 : L1= {b} Langkah 2 : Jika χL1, maka χaL1 dan χbL1.
Teori Bahasa dan Automata | 16
Langkah 3 : Jika χL1, maka χaL. Ulangi langkah 2. Simulasi Langkah 1 : L1= {b} Langkah 3 : bL1, maka baL. L= {ba} Langkah 2 : Karena bL1, maka baL1 dan bbL. Langkah 3 : Karena baL1, maka baaL. Karena bbL1, maka baaL. L= {ba,baa,bba} Ulangi langkah 2. Karena baL1, maka baaL1 dan babL1. Langkah 3 : Karena baaL1, maka baaaL. Karena babL1, maka babaL. L= {ba,baa,bba,baaa,baba} Dan seterusnya... Maka akan diperoleh L adalah bahasa yang setiap stringnya berawal ˈbˈ berakhir ˈaˈ
Teori Bahasa dan Automata | 17
Latihan L adalah bahasa yang setiap stringnya memuat 1 ˈbˈ. Dan buatkan definisi rekursinya. Tugas Individu 1. ∑= {a,b} L adalah bahasa yang setiap stringnya memuat ˈbˈ berakhir
ˈaˈ.
Maka
buatlah
bentuk
bahasa
regulernya. 2. Buatlah definisi rekursi dari bahasa L tersebut dan lakukan simulasinya.
Teori Bahasa dan Automata | 18
EKSPRESI REGULER A. Ekspresi Reguler Ekspresi reguler adalah suatu ekspresi yang diperoleh dari definisi rekursi. Aturan: 1. Jika χ∑ maka χ adalah E.R 2. Jika χ adalah E.R maka χ˟ adalah E.R 3. Jika χ dan Y adalah E.R maka a) Χ+Y adalah E.R b) X˳Y adalah E.R Contoh : ∑= {a,b} Tunjukkan bahasa (a+b)˟ ab˟ adalah E.R Jawab: Dari aturan 1 : Karna a∑ maka a adalah E.R Karna b∑ maka b adalah E.R Dari aturan 3a : Karna a dan b adalah E.R. maka a+b adalah E.R
Teori Bahasa dan Automata | 19
Dari aturan 2 : Karna a+b adalah E.R. maka (a+b)˟ adalah E.R Dari aturan 3b Karna a+b adalah E.R. maka (a+b)˟a adalah E.R Dari aturan 2 : Karna b adalah E.R. maka b˟ adalah E.R Dari aturan 3b : Karna (a+b)˟a dan b˟
adalah E.R. maka
(a+b)˟ab˟ adalah E.R Jadi (a+b)˟ab˟ adalah E.R Latihan ∑= {a,b} Tunjukkan bahasa a˟ba+a(a+b)˟ adalah E.R.
Teori Bahasa dan Automata | 20
AUTOMATA A. Automata Automata adalah suatu sistem yang terdiri dari : 1. Kumpulan input didalam ∑. 2. Kumpulan state(keadaan) dimana 1 state diantaranya terdiri dari state awal dab beberapa state biasa serta beberapa state akhir. 3. Terdapat Tabel Transisi state yaitu tabel yang menunjukkan perpindahan state ke state lain, diakibatkan state sebelumnya diberikan input. Dimana state awal adalah keadaan awal, yaitu proses awal dari automata. Sedangkan state akhir adalah keadaan akhir, yaitu proses akhir dari automata.
B. Simbol/Lambang 1. Jika x adalah state awal, maka disimbolkan sebagai –x.
Teori Bahasa dan Automata | 21
2. Jika y adalah state akhir, maka disimbolkan sebagai +y. 3. Jika state x diberi input a menuju ke state y. Maka disimbolkan x
a
y
Teori Bahasa dan Automata | 22
Contoh 1 : 1. Kumpulan input : ∑= {a,b} 2. Kumpulan state S : {x,y,z} Dimana dimisalkan x sebagai state awal dan z sebagai state akhir. 3. Tabel transisi state dimisalkan sebagai berikut : State
a
b
-x
y
x
y
x
z
z
y
z
4. Automata dapat digambarkan sebagai berikut : b
a
-x
y
a
b
+z
b
a
Suatu string dikatakan diterima oleh automata jika string tersebut dibaca dari state awal, maka akan berakhir di state akhir. Contoh : Dari automata diatas, misal dibaca string “baaabab”. Pembacaannya harus dimulai dari state awal.
-x
b
-x
a
y
a
-x
a
y
b
+z
a
y
b
+z
Karna pembacaan “baaabab” berakhir di state “+z” maka string tersebut diterima.
Teori Bahasa dan Automata | 23
Makassar, 8 November 2017 Contoh 2 : Diberikan automata : a
b
a
-x
+y
b
Tentukan bahasa yang diterima automata tersebut! Jawab : String
–
string
yang
diterima
automata
adalah
b {a,aa,ba,baa,bba,aaa,aba,baaa,aaba,...}
Jadi string – string yang diterima memiliki ciri – ciri string berakhiran ˈaˈ. Jadi bahasa yang diterima automata adalah bahasa yang setiap stringnya berakhiran ˈaˈ.
Contoh 3 : Diberikan automata : b
b -x
a
+y
a
Tentukan bahasa yang diterima automata ! Jawab : {a,ab,ba,bba,abb,bab,aaa,bbba,bbab,...} Jadi string – string yang diterima memiliki ciri – ciri string yang memuat ˈaˈ ganjil.
Teori Bahasa dan Automata | 24
Contoh 4 : Diberikan automata : a
b
b
-x
a
y
a +z
b
Tentukan bahasa yang diterima automata ! Jawab : {ba,aba,baa,aaba,abaa,baaa,bbba,...} Jadi string – string yang diterima memiliki ciri – ciri string yang memuat ˈbˈ ganjil dan berakhiran ˈaˈ. Latihan Diberikan automata : b a
-x
b
y b
a
+z
a
Tentukan bahasa yang diterima automata ! Cara membuat automata dan bahasa yang tidak diketahui Diberikan bahasa L yang dibuat dari alfabet ∑. Langkah – langkah membuat automata yang menerima bahasa ˈLˈ adalah sebagai berikut :
Teori Bahasa dan Automata | 25
1. Buatlah Transisi State yang menerima string terpendek dari ˈLˈ. 2. Lengkapi setiap state didalam transisi state dengan semua input yang ada dalam ∑ sehingga akan menjadi automata yang menerima bahasa ˈLˈ. 3. Jika tidak ada state yang cocok. Maka tambahkan dengan state yang baru.
Teori Bahasa dan Automata | 26
Contoh : ∑= {a,b} L adalah bahasa yang setiap stringnya memuat ˈbˈ ganjil dan berakhiran ˈaˈ ganjil. Buatlah automata yang menerima bahasa ˈLˈ tersebut. Jawab : 1. String terpendek L= ˈbaˈ. Transisi State yang menerima ˈbaˈ -x
b
y
a
+z
2. Melengkapi state – state dalam automata dengan input – input dari ∑, yaitu : a
-x
a
b
y
a
+z
b b Automata yang dapat menerima bahasa ˈLˈ
String
–
string
yang
diterima
adalah
{ba,aba,aaba,bbba,babba,...}
Latihan L adalah bahasa yang setiap stringnya berakhiran ˈaaˈ. Buatlah automata yang menerima bahasa ˈLˈ.
Teori Bahasa dan Automata | 27
Contoh 1 : L adalah bahasa yang setiap stringnya berawal ˈaˈ memuat ˈbˈ genap. Buatlah automata yang menerima bahasa ˈLˈ tersebut. Jawab : 1. L= {a,aa,abb,aaa,abba,aabb,aaaa,...} a
2. Automata : -x
a
+y
a b
w
b
b z
a
b
Teori Bahasa dan Automata | 28
Contoh 2 : ∑= {a,b} Buatlah automata yang menerima dan semua string memuat ˈaˈ ganjil dan ˈbˈ ganjil serta berakhiran ˈbˈ. Jawab : 1. {ab,abbb,aaab,babb,bbab,...} 2. Automata : a
-x
b
y
a
b
b
b
+z
b a
t
a
w
a
Jadi string – string yang diterima memiliki ciri – ciri string yang berakhiran ˈbˈ genap.
Latihan ∑= {a,b} Buatlah automata yang menerima semua string yang memuat ˈaˈ ganjil dan ˈbˈ ganjil serta berakhiran ˈabˈ
Teori Bahasa dan Automata | 29
Makassar, 29 November 2017
TEORI KLEENE A. Teori Kleene 1 Jika A adalah automata yang menerima bahasa L maka dapat dibuat automata yang menerima bukan bahasa L (ditulis Lʿ, dibaca L komplemen). Aturan untuk membuat automata yang bukan atau tidak dapat menerima bahasa L. 1. Setiap state akhir didalam automata A diubah menjadi state biasa. 2. Setiap state yang bukan state akhir diiubah menjadi state akhir.
Teori Bahasa dan Automata | 30
Contoh 1 : Diberikan automata yang menerima bahasa ˈLˈ sebagai berikut:
a
-x
y
b
+z
b
a b
b
a
a t
Maka automata yang tidak menerima bahasa L (Lʿ) adalah a
+x
+y
b
z
b
a b
b
a
a +t
Teori Bahasa dan Automata | 31
Contoh 2 : ∑= {a,b} Buatlah automata yang tidak dapat menerima string – string yang memuat ˈaˈ ganjil dan berakhiran ˈabˈ. Jawab : Misal L adalah bahasa yang setiap stringnya memuat ˈaˈ ganjil dan berakhiran ˈabˈ. Maka automata yang menerima bahasa L adalah a b
a
-x
b
y
+z
Menerima Bahasa L
a b a
b
t
Automata yang tidak dapat menerima bahasa L adalah a
b
a
+x
+y
b
z
Tidak menerima Bahasa L
a b a
b +t
Latihan ∑= {a,b}
Teori Bahasa dan Automata | 32
Buatlah automata yang tidak dapat menerima string – string yang memuat ˈbˈ ganjil dan berakhiran ˈabˈ.
B. Teori Kleene 2 Jika A1 adalah automata yang menerima bahasa L1 dan A2 adalah automata yang menerima L2. Maka dapat dibuat automata yang menerima bahasa L1 dan L2 (L1+L2). Misalkan x0,x1,x2,...xn. dengan X0 sebagai state awal dari automata A1 dan y0,y1,y2,...ym. dengan Y0 sebagai state awal dari automata A2. Dan z0,z1,z2,...zk adalah state – state dari automata yang menerima bahasa L1+L2. Maka aturan untuk membuat automata yang menerima bahasa L1+L2 adalah : 1. Jika z0 sebagai state awal, maka z0= x0+y0 2. Jika zk= xs+yt dan xs atau yt adalah state akhir, maka zk menjadi state akhir.
Teori Bahasa dan Automata | 33
Contoh : ∑= {a,b} Buatlah automata yang menerima string – string berakhiran ˈabˈ atau string – string yang memuat ˈbˈ ganjil. Jawab : Misal L1 adalah bahasa yang setiap stringnya berakhiran ˈabˈ dan L2 adalah bahasa yang setiap stringnya memuat ˈbˈ ganjil. Automata yang menerima bahasa L1 (berakhiran b a ˈabˈ)adalah : a
-x0
b
x1
a
+x2
Tabel Transisi state :
b
State a b -x0 x1 x0 x1 x1 x2 +x2 x1 x0 Automata yang menerima bahasa L2 (memuat ˈbˈ a a: ganjil)adalah -y0
b b
+y1
State -x0 x1 +x2
a x1 x1 x1
b x0 x2 x0
Teori Bahasa dan Automata | 34
Misal Z0 sebagai state awal dari automata yang menerima bahasa L1+L2. Berari Z0= X0+Y0 Definisi Operasi State Jika state Z= X+Y dan state Z diberi input ˈaˈ maka state X diberi input ˈaˈ dan state Y diberi input ˈaˈ. Ditulis Z+a= (X+a) + (Y+a) Proses Transisi State 1. Z0 diberi input ˈaˈ Z0+a= (X0+a) + (Y0+a) = X1 + Y0 Misal Z0+a= Z1, jadi Z1= X1 + Y0 2. Z0 diberi input ˈbˈ Z0+b= (X0+b) + (Y0+b) = X0 + Y1 Misal Z0+b= Z2, jadi Z2= X0 + Y1 Karna Y1 adalah state akhir, maka Z2 menjadi state akhir (berdasarkan aturan 2) 3. Z1 diberi input ˈaˈ Z1+a= (X1+a) + (Y0+a) = X1 + Y0 Jadi, Z1+a= Z1 4. Z1 diberi input ˈbˈ Z1+b= (X1+b) + (Y0+b) = X2 + Y1
Teori Bahasa dan Automata | 35
Misal Z1+b= Z3, jadi Z3= X2 + Y1 Karna Y1 adalah state akhir, maka Z3 menjadi state akhir (berdasarkan aturan 2) 5. Z2 diberi input ˈaˈ Z2+a= (X0+a) + (Y1+a) = X1 + Y1 Misal Z2+a= Z4, jadi Z4= X1 + Y1 Karna Y1 adalah state akhir, maka Z4 menjadi state akhir (berdasarkan aturan 2) 6. Z2 diberi input ˈbˈ Z2+b= (X0+b) + (Y1+b) = X0 + Y0 Jadi, Z2+b= Z0 7. Z3 diberi input ˈaˈ Z3+a= (X2+a) + (Y1+a) = X1 + Y1 Jadi, Z3+a= Z4 8. Z3 diberi input ˈbˈ Z3+b= (X2+b) + (Y1+b) = X0 + Y0 Jadi, Z3+b= Z0
Teori Bahasa dan Automata | 36
9. Z4 diberi input ˈaˈ Z4+a= (X1+a) + (Y1+a) = X1 + Y1 Jadi, Z4+a= Z4 10. Z4 diberi input ˈbˈ Z4+b= (X1+b) + (Y1+b) = X2 + Y0 Misal Z4+b= Z5, jadi Z5= X2 + Y0 Karna X2 adalah state akhir, maka Z5 menjadi state akhir (berdasarkan aturan 2) 11. Z5 diberi input ˈaˈ Z5+a= (X2+a) + (Y0+a) = X1 + Y0 Jadi, Z5+b= Z1 12. Z5 diberi input ˈbˈ Z5+b= (X2+b) + (Y0+b) = X0 + Y1 Jadi, Z5+b= Z2 Jadi diperoleh tabel transisi state sebagai berikut : State
a
b
-Z0
Z1
Z2
Z1
Z1
Z3
+Z2
Z4
Z0
Teori Bahasa dan Automata | 37
+Z3
Z4
Z0
+Z4
Z4
Z5
+Z5
Z1
Z2
Automata yang menerima bahasa L1+L2 a z1 b
a
+z3
-z0 b
a
b
a
a a
+z2
+z4
b
b +z5
Teori Bahasa dan Automata | 38
C. Teori Kleene 3
Makassar, 2017
6
Desember
Jika A1 adalah automata yang menerima bahasa L1 dan A2 adalah automata yang menerima L2. Maka dapat dibuat automata yangMenerima menerima L1˳L2 (L1 dikonkatenasi Bahasabahasa L1 L2).
-x0
Automata A1
+xn -y0
Automata A2
+ym
Menerima Bahasa L2
Misalkan x0,x1,x2,...xn. dengan X0 sebagai state awal dari automata A1 dan y0,y1,y2,...ym. dengan Y0 sebagai state awal dari automata A2. Dan z0,z1,z2,...zk adalah state – state dari automata yang menerima bahasa L1˳L2. Maka aturan untuk membuat automata
yang
menerima bahasa L1˳L2 adalah : 1. Jika z0 sebagai state awal, maka z0= x0 2. Jika zk= xs+yt, maka zk menjadi state akhir jika yt adalah state akhir.
Teori Bahasa dan Automata | 39
3. Jika zk= xs+yt dan xs sebagai state akhir, maka zk harus ditambah y0, sehingga zk= xs+y0+yt.
Teori Bahasa dan Automata | 40
Contoh : ∑= {a,b} L1 adalah bahasa yang setiap stringnya memuat ˈaˈ ganjil berakhiran ˈbaˈ. L2 adalah bahasa yang setiap stringnya berakhiran ˈbˈ ganjil. Buatlah automata yang menerima bahasa L1˳L2 Jawab : Automata yang menerima bahasa L1 (memuat ˈaˈ ganjil berakhiran ˈbaˈ) adalah : Tabel transisi state :
b b
-x0
x1
+x2
a
a
a
a
b
x3
state -x0 x1 +x2 x3
a x3 x2 x0 x0
b x1 x1 x3 x3
b
Automata yang menerima bahasa L2 (berakhiran ˈbˈ ganjil) adalah : b a
-y0
b
+y1
state -y0 +y1
a y0 y0
b y1 y0
a
Misal Z0 sebagai state awal dari automata yang menerima bahasa L1˳L2. Berari Z0= X0 (dari aturan 1)
Teori Bahasa dan Automata | 41
Proses Transisi State 1. Z0 diberi input ˈaˈ Z0+a= X0+a = X1 Misal Z0+a= Z1, jadi Z1= X3 2. Z0 diberi input ˈbˈ Z0+b= X0+b = X1 Misal Z0+a= Z2, jadi Z2= X1 3. Z1 diberi input ˈaˈ Z1+a= X3+a = X0 Jadi, Z1+b= Z0 4. Z1 diberi input ˈbˈ Z1+b= X3+b = X3 5. Z2 diberi input ˈaˈ Z2+a= X1+a = X2 Jadi, Z1+b= Z1 Misal Z2+a= Z3, jadi Z3= X2 Tapi karena X2 adalah state akhir maka Z3 ditambah Y0 menjadi Z3= X2+Y0 (dari aturan 3)
Teori Bahasa dan Automata | 42
6. Z2 diberi input ˈbˈ Z2+b= X1+b = X1 Jadi, Z2+b= Z2 7. Z3 diberi input ˈaˈ Z3+a= (X0+a )+(Y0+a) = X0+Y0 Misal Z3+a= Z4, jadi Z4= X0+Y0 8. Z3 diberi input ˈbˈ Z3+b= (X0+b )+(Y0+b) = X3+Y1 Misal Z3+b= Z5, jadi Z5= X3+Y1 Tapi karena Y1 adalah state akhir maka Z5 menjadi state akhir (dari aturan 2) 9. Z4 diberi input ˈaˈ Z4+a= (X0+a )+(Y0+a) = X3 + Y0 Misal Z4+a= Z6, jadi Z6= X3 + Y0 10. Z4 diberi input ˈbˈ Z4+b= (X0+b )+(Y0+b) = X1 + Y1 Misal Z4+b= Z7, jadi Z7= X1+Y1
Teori Bahasa dan Automata | 43
Tapi karena Y1 adalah state akhir maka Z7 menjadi state akhir (dari aturan 2) 11. Z5 diberi input ˈaˈ Z5+a= (X3+a )+(Y1+a) = X0 + Y0 Jadi, Z5+a= Z4 12. Z5 diberi input ˈbˈ Z2+b= (X3+b )+(Y1+b) = X3 + Y0 Jadi, Z5+b= Z6 13. Z6 diberi input ˈaˈ Z6+a= (X3+a )+(Y0+a) = X0 + Y0 Jadi, Z6+a= Z4 14. Z6 diberi input ˈbˈ Z6+b= (X3+b )+(Y0+b) = X3 + Y1 Jadi, Z6+b= Z5 15. Z7 diberi input ˈaˈ Z7+a= (X1+a )+(Y1+a) = X2+Y0 Jadi, Z7+a= Z3
Teori Bahasa dan Automata | 44
16. Z7 diberi input ˈbˈ Z7+b= (X1+b )+(Y1+b) = X1+Y0 Misal Z7+b= Z8, jadi Z8= X1+Y0 17. Z8 diberi input ˈaˈ Z8+a= (X1+a )+(Y0+a) = X2 + Y0 Jadi, Z8+a= Z3 18. Z8 diberi input ˈbˈ Z8+b= (X1+b )+(Y0+b) = X1 + Y1 Jadi, Z8+b= Z7 Jadi diperoleh tabel transisi state sebagai berikut : State -Z0 Z1 Z2 Z3 Z4 +Z5 Z6 +Z7 Z8
a Z1 Z0 Z3 Z4 Z6 Z4 Z4 Z3 Z3
b Z2 Z2 Z2 Z5 Z7 Z6 Z5 Z8 Z7
Teori Bahasa dan Automata | 45
Automata yang menerima bahasa L1˳L2 b a
Z1 a +Z5
-Z0 b
Z2
b
b
b a
Z3
a
b
Z4
a
a a a Z8
a b
b
Z6
b +Z7
Teori Bahasa dan Automata | 46
AUTOMATA BEROUTPUT A. Automata Beroutput Automata beroutput adalah yang mempunyai input dan output, tapi tidak mempunyai state akhir. Jenis automata beroutput antara lain: 1. Mesin Moore 2. Mesin Mealy B. Mesin Moore Mesin Moore adalah automata beroutput yang outputnya ada di dalam setiap statenya. 1. Input Mesin Moore berbentuk ∑= {a,b} 2. Output Mesin Moore berbentuk Ʈ= {0,1} (dibaca tho)
Teori Bahasa dan Automata | 47
Contoh : Output: X,Y,Z
b
Input: a,b
y
/0
a -x
/1
a b a
z
Misal diberi input ˈbabbaaˈ
Maka outputnya :
/1
b
ˈ111110ˈ
-x
b
a
z 1
x 1
b
z
b
1
z 1
a
x 1
a
y 0
C. Mesin Mealy Mesin Mealy adalah automata beroutput yang
outputnya
disajikan
bersama
dengan
inputnya.
Teori Bahasa dan Automata | 48
Contoh :
b a
/1 a
-x
b
/0 y b
/0
/1
/0
z Misal diberi input ˈaabbabˈ
Maka outputnya : ˈ101001ˈ a
-x
a
y
1
0
z
b 1
y
b 0
y
a
z
0
b
y
1
Hukum : 1. Setiap Mesin Moore dapat diubah menjadi Mesin Mealy. Caranya : x
/0
a
y
Mesin Moore
/1
a
x
/1
y
Mesin Mealy
Teori Bahasa dan Automata | 49
Contoh :
Diberikan Mesin Moore sebagai berikut : b y
a
/1
a -x
b
/0
b a
z
/0
Outputnya : ˈ1001ˈ
Bentuk Mesin Mealynya sebagai berikut : b
/1
a
/0
y a
/1 b
-x
/1
b
/0
a
/0
z
Input : ˈaabbˈ Outputnya : ˈ1001ˈ
Teori Bahasa dan Automata | 50
2. Setiap Mesin Mealy dapat diubah menjadi Mesin Moore.
Kasus 1 : b
/1
b x
a
x
/1
/1
a Mesin Mealy
Mesin Moore
Kasus 2 : a
/1
b
/1 x
a
a
b X
/1
/1
Xs/0 a
Xs adalah state salinan dari X
Mesin Mealy
Mesin Moore
Kasus 3 : b
/1
a
/0
a
b
/1
a x
/1
x
a
b
/0
b
xs/1
a Mesin Mealy
Mesin Moore
Teori Bahasa dan Automata | 51
Contoh : Ubahlah Mesin Mealy berikut menjadi Mesin Moore. a b
/0 -x a
/1
y
b
/0
/0
Output yang menuju state X adalah ˈ0ˈ. Sedangkan output yang menuju ke state Y adalah 0 dan 1 dan mempunyai looping. Jawab : Bentuk Mesin Moorenya adalah : y b -x/0 a /1 a b
a
y s/ 1
b
Teori Bahasa dan Automata | 52
Makassar, 2017
D. Transduser
13
Desember
Transduser adalah rangkaian gerbang logika yang dapat diubah menjadi automata beroutput Mesin Mealy.
Gerbang – gerbang logika X 1 1 0 0
Gerbang ˈORˈ Y X ˈORˈ Y 1 1 0 1 1 1 0 0
X 1 1 0 0
Gerbang ˈNORˈ Y X ˈORˈ Y 1 0 0 0 1 0 0 1
X 1 1 0 0
Gerbang ˈXORˈ Y X ˈORˈ Y 1 0 0 1 1 1 0 0
X 1 1 0 0
Gerbang ˈANDˈ Y X ˈANDˈ Y 1 1 0 0 1 0 0 0
Gerbang ˈNANDˈ X Y X ˈORˈ Y 1 1 0 1 0 1 0 1 1 0 0 1 Gerbang ˈNOTˈ X NOT (X) 1 0 0 1
Teori Bahasa dan Automata | 53
Contoh : Input
A
AND
B
OR
XOR
XOR
Output
NOT
Cara merubah transduser menjadi Mesin Mealy : Langkah 1 : Menentukan nama – nama state yang tergantung dari nilai simpul A dan simpul B pada transduser, yaitu : Nilai A
Nilai B
Nama State
0
0
X
0
1
Y
1
0
Z
1
1
T
Langkah 2 : Merumuskan ABaru, BBaru dan output yang berdasarkan gambar transdusernya. Maka dapat dirumuskan:
Teori Bahasa dan Automata | 54
Abaru = Input AND (ALama XOR NOT (BLama)) BBaru = Input OR ALama Output = Input XOR BLama Langkah 3 : Melakukan proses transisi state. 1. State X diberi input ˈ0ˈ (Alama = 0, Blama = 0) ABaru
= 0 AND (0 XOR NOT (0)) = 0 AND (0 XOR 1) = 0 AND 1 =0 BBaru = 0 OR 0 =0 Output = 0 XOR 0 =0 Karna ABaru= 0 dan BBaru= 0, maka dari tabel state diperoleh sebagai state X. 0/0 Transisi Statenya adalah x 2. State X diberi input ˈ1ˈ (Alama = 0, Blama = 0) ABaru
= 1 AND (0 XOR NOT (0)) = 1 AND (0 XOR 1) = 1 AND 1 =1 BBaru = 1 OR 0 =1 Output = 1 XOR 1 =0
Teori Bahasa dan Automata | 55
Karna ABaru= 1 dan BBaru= 1, maka dari tabel state diperoleh sebagai state T. x
Transisi Statenya adalah
1
/1
T
3. State Y diberi input ˈ0ˈ (Alama = 0, Blama = 1) ABaru
= 0 AND (0 XOR NOT (1)) = 0 AND (0 XOR 0) = 0 AND 0 =0 BBaru = 0 OR 0 =0 Output = 0 XOR 1 =1 Karna ABaru= 0 dan BBaru= 0, maka dari tabel state diperoleh sebagai state X. Transisi Statenya adalah Y
0
/1
X
4. State Y diberi input ˈ1ˈ (Alama = 0, Blama = 1) ABaru
= 1 AND (0 XOR NOT (1)) = 1 AND (0 XOR 0) = 1 AND 0 =0 BBaru = 1 OR 0 =1 Output = 1 XOR 1 =0 Karna ABaru= 0 dan BBaru= 1, maka dari tabel state diperoleh sebagai state Y. Transisi Statenya adalah
1/
0
Y
Teori Bahasa dan Automata | 56
5. State Z diberi input ˈ0ˈ (Alama = 1, Blama = 0) ABaru
= 0 AND (1 XOR NOT (0)) = 0 AND (1 XOR 1) = 0 AND 0 =0 BBaru = 0 OR 1 =1 Output = 0 XOR 0 =0 Karna ABaru= 0 dan BBaru= 1, maka dari tabel state diperoleh sebagai state . Transisi Statenya adalah Z
0
/0
Y
6. State Z diberi input ˈ1ˈ (Alama = 1, Blama = 0) ABaru
= 1 AND (1 XOR NOT (1)) = 1 AND (1 XOR 1) = 1 AND 0 =0 BBaru = 1 OR 1 =1 Output = 1 XOR 0 =1 Karna ABaru= 0 dan BBaru= 1, maka dari tabel state diperoleh sebagai state Y. Transisi Statenya adalah Z
1
/1
Y
7. State T diberi input ˈ0ˈ (Alama = 1, Blama = 1) ABaru
= 0 AND (1 XOR NOT (1)) = 0 AND (1 XOR 0) = 0 AND 1 =0
Teori Bahasa dan Automata | 57
BBaru
= 0 OR 1 =1 Output = 0 XOR 1 =1 Karna ABaru= 0 dan BBaru= 1, maka dari tabel state diperoleh sebagai state Y.
0
/1
T
Transisi Statenya adalah
Y
8. State T diberi input ˈ1ˈ (Alama = 1, Blama = 1) ABaru
= 1 AND (1 XOR NOT (1)) = 1 AND (1 XOR 0) = 1 AND 1 =1 BBaru = 1 OR 1 =1 Output = 1 XOR 1 =0 Karna ABaru= 1 dan BBaru= 1, maka dari tabel state diperoleh sebagai state T.1/0 Transisi Statenya adalah T Setelah langkah selesai, transisi statenya disusun menjadi automata beroutput Mesin Mealy. 1
X
0
/0
/1
T
1
/0
0 0
/1
/1 0
1
/0
/0
Y
Z
1
/1
Teori Bahasa dan Automata | 58
Dari gambar diatas (Mesin Mealy) tersebut disimpulkan state Z menjadi state awal, karena jika selain Z menjadi state awal, maka state Z tidak dapat dicapai. Tugas Individu ∑= {a,b}
L1 adalah bahasa yang setiap stringnya memuat ˈaˈ ganjil berakhir ˈbbˈ.
L2 adalah bahasa yang setiap stringnya berakhir ˈabˈ.
Buatlah automata yang menerima : a) Bahasa L1+L2 b) Bahasa L1˳L2
Teori Bahasa dan Automata | 59
MID Soal
FINAL Makassar, 20 Desember 2017
Soal 1. Diberikan transduser sebagai berikut : NOT
Input
OR
NOT
A
XOR
B
NOR
Output
NOT
AND
Ubahlah transduser menjadi automata Mesin Mealy! 2. ∑= {a,b}
L1 adalah bahasa yang setiap stringnya memuat ˈaˈ ganjil berakhir ˈabˈ.
L2 adalah bahasa yang setiap stringnya berakhir ˈaaˈ.
Teori Bahasa dan Automata | 60
Buatlah automata yang menerima : Bahasa L1˳L2 (Teori Kleene 3)
Teori Bahasa dan Automata | 61