Teori Bahasa Dan Otomata.docx

BAHAN 1 – KONSEP BAHASA PENDAHULUAN 

 

Ilmu Komputer memiliki dua komponen utama : 1. Model dan gagasan mendasar mengenai komputer 2. Teknik rekayasa untuk perancangan sistem komputer meliputi perangkat keras (hardware) dan perangkat lunak (software) Teori bahasa & otomata termasuk dalam bagian pertama dari 2 komponen utama Ilmu Komputer di atas. Teori bahasa dan otomata diterapkan pada perancangan digital, pembuatan bahasa pemrograman, dan kompilator

ABJAD, UNTAI (STRING), BAHASA  

Sebuah simbol adalah suatu entitas abstraks yang tidak didefinisikan secara formal Contoh : huruf dan digit adalah simbol yang dipakai Abjad (alphabet) adalah sebuah himpunan berhingga tak kosong dari simbol–simbol Notasi : Σ Contoh : - Abjad terdiri dari 26 simbol : Σ = {a,b,c,d, … z} a  Σ, artinya a adalah sebuah simbol di dalam Σ - Σ = {1,2,3,4,5,6,7,8,9} a∉Σ Jika Σ1 dan Σ2 adalah abjad-abjad maka Σ1  Σ2, Σ1 – Σ2, dan Σ2 – Σ1 merupakan









himpunan tidak kosong (abjad) Untai / string / kata adalah sebuah barisan berhingga simbol-simbol dari suatu abjad. Contoh : Diketahui abjad Σ={a,b} maka string yang bisa terjadi a, ab, aa, bb, aaa, bbb, aaab, dst String kosong adalah barisan yang kosong dari simbol-simbol, notasi = {} Bahasa (language) adalah suatu kumpulan dari string-string, notasi = L Contoh : Diketahui : ∑= {1,2,3,4,…,5} Kumpulan {1,12,123,1234,12345,112} adalah sebuah bahasa berdasarkan abjad yang terdiri dari digit-digit itu. Diketahui : ∑= {1} Kumpulan {1,11,111,1111, ….} adalah sebuah bahasa Bahasa kosong (empty language) adalah sebuah bahasa yang tidak terdiri dari stringstring. Bahasa kosong berbeda dengan bahasa yang terdiri dari string kosong. Notasi = ∅ Jika ∑ merupakan sebuah abjad maka ∑ juga sebuah bahasa yang terdiri atas semua string simbol tunggal. Misal ∑ adalah sebuah abjad dan s adalah suatu string berdasarkan ∑. Jika L adalah suatu bahasa yang terdiri dari beberapa string berdasarkan ∑ dan jika s adalah sebuah string di dalam L maka dapat ditulis : s  L, artinya s adalah elemen dari L Contoh : 121  {1,12,121,1212,12121}

Teori Bahasa & Automata –Hal. 1



Bahasa universal (universal language) dari ∑ adalah bahasa yang terdiri dari semua string berdasarkan suatu abjad ∑. Notasi : ∑* Contoh : ∑ = {1}, maka ∑* = {,1,11,111,1111, …} Untuk abjad apa saja, ∑* bersifat tak berhingga karena abjad-abjadnya tidak kosong.

OPERASI – OPERASI PADA STRING 1. Panjang (length) dari string Panjang string s didefinisikan sebagai banyaknya anggota abjad (termasuk yang sama) dalam s. Notasi : |s| Contoh : ∑ = {1,2} s1 = 111 maka | s1| = 3 s2 = 121 maka | s2| = 3 s3 = 121212 maka |s3| = 6 2. Perangkaian/konkatenasi (Concatenation) Jika s1 dan s2 adalah string-string, perangkaian s1 dan s2 adalah string yang diperoleh dengan merekatkan string s2 ke string s1 Contoh : s1 = 112 dan s2 = 121212, maka perangkaian s1 dengan s2 adalah string 112121212 s1. s2 = s1s2 = 112121212 s1. ε = s1 = 112 Sifat – sifat konkat 1. .s = s. = s, s  string 2. |s1s2| = |s1|+|s2| 3. sk = s.sk-1 , dengan s0 =  ,  k = 1, 2, … 4. (s1s2)s3 = s1(s2s3) = s1s2s3 5. s1s2 ≠ s2s1 3. Eksponensiasi/Pangkat (Exponentiation) Misalkan s merupakan sebuah string atau kata, maka : o

s =ε 1

s = 122 2

s = 122122 3

s = 122122122 OPERASI – OPERASI PADA BAHASA 1. Perangkaian (Concatenation) Misal L1 dan L2 merupakan bahasa-bahasa berdasarkan abjad. Perangkaian L1 dan L2 ditulis : L1 . L2 = { s1. s2 | s1  L1 dan s2  L2} Contoh : L1 = {cat,dog} dan L2 = {house}, maka : L1 . L2 = {cathouse, doghouse} L1.(ε) = (ε) . L1 = L1

Teori Bahasa & Automata –Hal. 2

Sifat – sifat konkatenasi bahasa 1. ∅L = L∅= ∅ L∑* = ∑*(L) =∑* 2. L1L2 ≠ L2L1 kecuali L1 = L2 3. (L1L2)L3 = L1(L2L3) = L1L2L3 4. Distributif L1(L2 ∪ L3) = L1L2 ∪ L1L3 L1(L2 ∩ L3) = L1L2 ∩ L1L3

2. Eksponensiasi (Exponentiation) Misalkan L merupakan suatu bahasa berdasarkan abjad ∑ : Contoh : Jika L = {ab} berdasarkan abjad tersebut didapatkan : o

L = {ε} 1

L = L = {ab} 2

1

3

2

L = L.L = {abab} L = L.L = {ababab} 3. Gabungan (Union) Misalkan L1 dan L2 adalah bahasa-bahasa berdasarkan suatu abjad ∑, maka union dari L1 dan L2 (L1  L2) terdiri dari semua string/kata yang muncul sekurangkurangnya sekali dalam L1 dan L2. L1  L2 = {s|s  L1 atau s  L2} 4. Irisan (Intersection) Misalkan L1 dan L2 adalah bahasa-bahasa berdasarkan suatu abjad ∑, maka intersection dari L1 dan L2 (L1 ∩ L2) terdiri dari string-string yang muncul baik di L1 maupun di L2 sekaligus. L1 ∩ L2 = {s|s  L1 dan s  L2} Contoh : ∑ = {0,1} Bahasa-bahasa L1 = {ε,0,1,10,11} dan L2 = {ε,1,0110,11010}, maka L1  L2 = {ε,0,1,10,11,0110,11010} L1 ∩ L2 = {ε,1} 5. Sub Bahasa Misalkan L1 dan L2 adalah bahasa-bahasa berdasarkan suatu abjad ∑ dan jika semua string di L1 juga merupakan string di L2, maka L1 disebut sebuah sub bahasa dari L2. Notasi L1  L2 Contoh : Jika L1 = {a,aa,aaa} dan L2 = {a,aa,aaa,aaaa,aaaaa}, maka L1  L2 6. Equal (Sama) Dua buah bahasa L1 dan L2 dikatakan sama jika kedua bahasa tersebut secara persis mempunyai string-string yang sama, artinya jika sebagai himpunan-himpunan keduanya persis sama. Notasi : L1 = L2

Teori Bahasa & Automata –Hal. 3

7. Star Closure dan Plus Closure Jika L adalah sebuah bahasa berdasarkan suatu abjad ∑, didefinisikan : • Star Closure dari L* : 

L*   Ln n0

+

• Plus Closure dari L : 



L   Ln n 1

Contoh : o

L = {ε} 1

L = {a} 2

2

3

3

L = {a }={aa} L = {a }= {aaa} dan seterusnya …… Jadi : 

L*   Ln n0

0

1

2

2

3

= L  L  L  …. = {ε}  {a}  {aa}  … = {ε, a, aa, …} 

L   Ln n 1

1

= L  L  L  …. = {a}  {aa}  {aaa}  … = {a, aa, aaa, …}

Teori Bahasa & Automata –Hal. 4

Sifat – sifat Star Closure 1. ε ∈ L* 2. 3. 4. 5. 6. 7.

∅* = {1} L+  L* Jika ε ∈ L → L+ = L* L1  L2 → L1*  L2* L1* ∪ L2*  (L1 ∪ L2)* L1* ∩ L2* = ( L1 ∩ L2 )*

Contoh: -

{1}* = {ε, 1, 11, 111, 1111, … }

-

{0}* = {ε, 0, 00, 000, 0000, … }

-

{0}* ∪ {1}* = {ε, 0, 00, … , 1, 11, 111, … }

-

({0} ∪ {1})* = {0,1}* = ∑*

Teori Bahasa & Automata –Hal. 5