PENGANTAR TEORI BAHASA DAN AUTOMATA - 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 manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat.
Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja. Bahasa Formal adalah suatu kalimat yang dibentuk dengan menerapkan serangkaian aturan produksi pada sebuah simbol “akar”. Proses penerapan aturan produksi dapat digambarkan sebagai suatu diagram pohon.
Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Teori Automata : studi tentang komputasi abstrak sebuah perangkat berbasis komputer atau mesin.
 |
| Credits: Ahwan0m.site |
Automata
Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Teori Automata : studi tentang komputasi abstrak sebuah perangkat berbasis komputer atau mesin.
Sebelum adanya komputer (1930), Alan Turing mempelajari sebuah mesin abstrak (Turing machine) yang memiliki semua kapabilitas yang dimiliki oleh sebuah komputer yang ada sekarang (tergantung pada pemakaiannya). Tujuannya adalah menggambarkan secara jelas batasan antara apa yang dapat dilakukan oleh sebuah mesin berbasis komputer dan apa yang tidak.
Beberapa contoh tipe mesin (finite automata) yang dipelajari oleh sejumlah peneliti dan berguna untuk berbagai macam keperluan. Dalam dunia matematika, automata berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input dan mengeluarkan output, dalam bentuk diskrit.
1. Regular Expression digunakan dalam berbagai sistem seperti : UNIX (a.*b), XML tags dengan format RE (person (name, addr, child*) )
2. Finite Automata Model Protocol , rangkaian elektronik ; teori digunakan untuk model-checking.
3. Contex-free Grammar digunakan untuk mendeskripsikan sintaks pada hampir seluruh bahasa pemrograman
Contoh:
Alphabet binary : ∑ = {0, 1}
Set dari semua huruf-huruf kecil : ∑ = {a, b, . . . , z}
Set dari semua karakter ASCII
Sebuah string (atau kadang disebut sebuah word) adalah deretan terbatas dari simbol-simbol terpilih dari sejumlah alphabet Contoh: 01101 dan 111 adalah string dari alphabet binari ∑ = {0, 1}
String hampa (null string)adalah sebuah string dengan nol kemunculan 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. Panjang sebuah string: jumlah posisi simbol dalam sebuah string
Contoh : 01101 memiliki panjang 5. Meskipun hanya ada dua simbol (0 dan 1) dalam string 01101, tetapi 5 posisi untuk simbol.
Notasi panjang w : | w |
Contoh: | 011 | = 3 dan l e l = 0
Jika ∑ adalah sebuah alphabet, kita dapat mengekspresikan sebuah set dari sejumlah string dengan panjang tertentu dari alphabet tersebut dengan menggunakan notasi eksponensial :
∑k : sebuah set string dengan panjang k, dengan setiap komponen simbol di dalamnya.
Contoh:
∑ 0 : {e}, tanpa memperhitungkan alphabet apapun di dalamnya. Hanya e yang merupakan string dengan panjang 0.
Jika ∑ = {0, 1}, then:
1. ∑ 1 = {0, 1}
2. ∑ 2 = {00, 01, 10, 11}
3. ∑ 3 = {000, 001, 010, 011, 100, 101, 110, 111}
Catatan : Penjelasan ∑ dan ∑ 1:
1. ∑ adalah sebuah alphabet; anggotanya adalah 0 and 1 yang merupakan simbol.
2. ∑ 1 adalah sebuah string; anggotanya adalah string yang masing-masing memiliki panjang 1.
Kleene Closure :
Positive Closure :
∑* : Sebuah set dari semua string yang terbentuk dari sekelompok
alphabet.
Simbol ∑ * disebut Kleene star dan diberi nama berdasarkan nama ahli matematika dan logika Stephen Cole Kleene.
sehingga ∑ *: = ∑ + ∪ {e}
Definisikan operasi biner yang disebut concatenation pada ∑* berikut ini :
Jika a1a2a3 . . . an dan b1b2 . . . bm adalah bagian ∑* ,
maka a1a2a3 . . . an.b1b2 . . . bm = a1a2a3 . . . anb1b2 . . . bm
Dapat dikatakan, sejumlah string dapat di-concatenate dengan string yang lain Jika x dan y membentuk string maka x.y menyatakan concatenation dari x dan y, yaitu string yang terbentuk dari tiruan x dan diikuti oleh tiruan y
Contoh:
1. x = 01101 and y = 110
Maka xy = 01101110 dan yx = 11001101
2. Untuk setiap string w, persamaan e w = w e = w .
Persamaan ini , e adalah identitas untuk concatenation
Jika S dan T adalah subsets dari ∑* , maka
S.T = {s.t | s ∈ S, t ∈ T}
Concatenation adalah penyambungan dua buah string. Operator Concatenation adalah concate atau tanpa lambang apapun. Contoh : concate (xy) = xy = abc123, Alternation adalah pilihan satu diantara dua buah string. Operator alternation adalah alternate atau | . Contoh alternate (xy) = x | y = abc atau 123
Diberikan dua string : x = abc, dan y = 123
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.
Operasi concatenation bersifat asosiatif :
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 :
Elemen identitas operasi alternation adalah dirinya sendiri : x | x = x
Sifat distributif concatenation terhadap alternation : x ( y | z) = xy | xz
Beberapa kesamaan :
Jika ∑ adalah sebuah alphabet, dan L ⊆ ∑* , maka L adalah sebuah (formal) bahasa pada ∑. Bahasa (Language): sebuah set dari string (kemungkinan tidak terbatas) yang komponennya dipilih dari beberapa ∑*. Sebuah bahasa pada ∑ boleh tidak mengikutkan semua string dengan semua symbol pada ∑. Maka, sebuah bahasa pada ∑ juga merupakan sebuah bahasa pada setiap alphabet yang merupakan superset dari ∑
Contoh:
• Bahasa Pemrograman C
Program-program yang legal adalah sebuah subset dari semua string yang mungkin dapat dibentuk dari alphabet sebuah bahasa (sebuah subset dari karakter ASCII)
• Bahasa Inggris atau Bahasa Perancis
Contoh Bahasa
1. Sebuah bahasa dari semua strings yang terdiri dari n buah 0 diikuti oleh n buah 1 (n ≥ 0): {e, 01, 0011, 000111, . . .}
2. Sebuah set dari strings terdiri dari sejumlah 0 dan 1 dengan jumlah yang sama : {e, 01, 10, 0011, 0101, 1001, . . .}
3. ∑* adalah sebuah bahasa untuk setiap alphabet ∑
4. ∅, adalah bahasa hampa (empty language), adalah sebuah bahasa untuk setiap alphabet
5. {e}, bahasa yang terdiri dari hanya string hampa (empty string), juga merupakan bahasa untuk setiap alphabet. Catatan : ∅ ≠ {e} karena ∅ tidak memiliki strings dan {e} memiliki satu string
6. {w | w terdiri dari sejumlah yang sama 0 dan 1}
7. {0 n1 n | n ≥ 1}
8. {0 I 1 j | 0 ≤ i ≤ j}
Concatenation dari bahasa (languages) L dan M, dinotasikan dengan L . M atau hanya LM , adalah sebuah set dari strings yang dapat dibentuk dengan mengambil string yang manapun dalam L dan menggabungkannya dengan string apapun dalam M
Contoh:
Jika L = {0, 1} maka L* adalah semua string dengan 0 dan 1
Jika L = {0, 11} maka L* terdiri dari string-string 0 dan 1 dimana 1 muncul secara berpasangan, e.g., 011, 11110 dan e. Tetapi bukan 01011 atau 101
Beberapa contoh tipe mesin (finite automata) yang dipelajari oleh sejumlah peneliti dan berguna untuk berbagai macam keperluan. Dalam dunia matematika, automata berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input dan mengeluarkan output, dalam bentuk diskrit.
Tujuan Mempelajari Teori Bahasa dan Otomata
 |
| Credits: Teknoiot |
1. Regular Expression digunakan dalam berbagai sistem seperti : UNIX (a.*b), XML tags dengan format RE (person (name, addr, child*) )
2. Finite Automata Model Protocol , rangkaian elektronik ; teori digunakan untuk model-checking.
3. Contex-free Grammar digunakan untuk mendeskripsikan sintaks pada hampir seluruh bahasa pemrograman
Dasar-dasar Teori Bahasa Automata
A. Alphabet
Alphabet adalah simbol-simbol yang tidak kosong (nonempty) dan terbatas. Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol. Simbol : ∑Contoh:
Alphabet binary : ∑ = {0, 1}
Set dari semua huruf-huruf kecil : ∑ = {a, b, . . . , z}
Set dari semua karakter ASCII
B. String
Sebuah string (atau kadang disebut sebuah word) adalah deretan terbatas dari simbol-simbol terpilih dari sejumlah alphabet Contoh: 01101 dan 111 adalah string dari alphabet binari ∑ = {0, 1}
String hampa (null string)adalah sebuah string dengan nol kemunculan 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. Panjang sebuah string: jumlah posisi simbol dalam sebuah string
Contoh : 01101 memiliki panjang 5. Meskipun hanya ada dua simbol (0 dan 1) dalam string 01101, tetapi 5 posisi untuk simbol.
Notasi panjang w : | w |
Contoh: | 011 | = 3 dan l e l = 0
Jika ∑ adalah sebuah alphabet, kita dapat mengekspresikan sebuah set dari sejumlah string dengan panjang tertentu dari alphabet tersebut dengan menggunakan notasi eksponensial :
∑k : sebuah set string dengan panjang k, dengan setiap komponen simbol di dalamnya.
Contoh:
∑ 0 : {e}, tanpa memperhitungkan alphabet apapun di dalamnya. Hanya e yang merupakan string dengan panjang 0.
Jika ∑ = {0, 1}, then:
1. ∑ 1 = {0, 1}
2. ∑ 2 = {00, 01, 10, 11}
3. ∑ 3 = {000, 001, 010, 011, 100, 101, 110, 111}
Catatan : Penjelasan ∑ dan ∑ 1:
1. ∑ adalah sebuah alphabet; anggotanya adalah 0 and 1 yang merupakan simbol.
2. ∑ 1 adalah sebuah string; anggotanya adalah string yang masing-masing memiliki panjang 1.
C. Kleen Closure dan Positive Closure
Kleene Closure :
X* = e | x | xx | xxx | … = e | x | x2 | x3 | …
Positive Closure :
x + = x | xx | xxx | … = x | x2 | x3 | …
∑* : Sebuah set dari semua string yang terbentuk dari sekelompok
alphabet.
{0, 1}* = {e, 0, 1, 00, 01, 10, 11, 000, . . .}
∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪ . . .
Simbol ∑ * disebut Kleene star dan diberi nama berdasarkan nama ahli matematika dan logika Stephen Cole Kleene.
∑ + = ∑1 ∪ ∑2 ∪ . . .
sehingga ∑ *: = ∑ + ∪ {e}
D. Concatenation
Definisikan operasi biner yang disebut concatenation pada ∑* berikut ini :
Jika a1a2a3 . . . an dan b1b2 . . . bm adalah bagian ∑* ,
maka a1a2a3 . . . an.b1b2 . . . bm = a1a2a3 . . . anb1b2 . . . bm
Dapat dikatakan, sejumlah string dapat di-concatenate dengan string yang lain Jika x dan y membentuk string maka x.y menyatakan concatenation dari x dan y, yaitu string yang terbentuk dari tiruan x dan diikuti oleh tiruan y
Contoh:
1. x = 01101 and y = 110
Maka xy = 01101110 dan yx = 11001101
2. Untuk setiap string w, persamaan e w = w e = w .
Persamaan ini , e adalah identitas untuk concatenation
Jika S dan T adalah subsets dari ∑* , maka
S.T = {s.t | s ∈ S, t ∈ T}
Concatenation adalah penyambungan dua buah string. Operator Concatenation adalah concate atau tanpa lambang apapun. Contoh : concate (xy) = xy = abc123, Alternation adalah pilihan satu diantara dua buah string. Operator alternation adalah alternate atau | . Contoh alternate (xy) = x | y = abc atau 123
Operasi Dasar String
Diberikan dua string : x = abc, dan y = 123
- Prefix string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.
- ProperPrefix string w adalah string yang dihasilkan dari string w denganmenghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.
- 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.
- ProperPostfix (atau ProperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut.
- Head string w adalah simbol paling depan dari string w.
- Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut.
- 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.
- 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.
- Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih- simbol-simbol dari string w tersebut
- ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atu lebih simbol-simbol dari string w tersebut.
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.
Sifat Aljabar Concatenation
Operasi concatenation bersifat asosiatif :
x ( y z ) = ( x y ) 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.
BAHASA
Jika ∑ adalah sebuah alphabet, dan L ⊆ ∑* , maka L adalah sebuah (formal) bahasa pada ∑. Bahasa (Language): sebuah set dari string (kemungkinan tidak terbatas) yang komponennya dipilih dari beberapa ∑*. Sebuah bahasa pada ∑ boleh tidak mengikutkan semua string dengan semua symbol pada ∑. Maka, sebuah bahasa pada ∑ juga merupakan sebuah bahasa pada setiap alphabet yang merupakan superset dari ∑
Contoh:
• Bahasa Pemrograman C
Program-program yang legal adalah sebuah subset dari semua string yang mungkin dapat dibentuk dari alphabet sebuah bahasa (sebuah subset dari karakter ASCII)
• Bahasa Inggris atau Bahasa Perancis
Contoh Bahasa
1. Sebuah bahasa dari semua strings yang terdiri dari n buah 0 diikuti oleh n buah 1 (n ≥ 0): {e, 01, 0011, 000111, . . .}
2. Sebuah set dari strings terdiri dari sejumlah 0 dan 1 dengan jumlah yang sama : {e, 01, 10, 0011, 0101, 1001, . . .}
3. ∑* adalah sebuah bahasa untuk setiap alphabet ∑
4. ∅, adalah bahasa hampa (empty language), adalah sebuah bahasa untuk setiap alphabet
5. {e}, bahasa yang terdiri dari hanya string hampa (empty string), juga merupakan bahasa untuk setiap alphabet. Catatan : ∅ ≠ {e} karena ∅ tidak memiliki strings dan {e} memiliki satu string
6. {w | w terdiri dari sejumlah yang sama 0 dan 1}
7. {0 n1 n | n ≥ 1}
8. {0 I 1 j | 0 ≤ i ≤ j}
Beberapa Operator Penting dalam Bahasa
UNION
Union dari dua buah bahasa (languages) L dan M, dinotasikan dengan L ∪ M, adalah sebuah set dari strings yang didalamnya terdiri dari salah satu L, atau M, atau keduanya.Contoh :
Jika L = {001, 10, 111} dan M = {e, 001} maka
L ∪ M = {e, 001, 10, 111}
CONCATENATION
Concatenation dari bahasa (languages) L dan M, dinotasikan dengan L . M atau hanya LM , adalah sebuah set dari strings yang dapat dibentuk dengan mengambil string yang manapun dalam L dan menggabungkannya dengan string apapun dalam M
Contoh :
Jika L = {001, 10, 111} dan M = {e, 001} maka
L.M = {001, 10, 111, 001001, 10001, 111001}
CLOSURE
Jika closure dari sebuah bahasa (language) L dinotasikan dengan L* dan merepresentasikan sebuah set dari sejumlah strings yang dapat dibentuk dengan mengambil sejumlah strings dari L, mungkin dengan repetisi (i.e., string yang sama dapat dipilih lebih dari sekali) dan menggabungkannya.Contoh:
Jika L = {0, 1} maka L* adalah semua string dengan 0 dan 1
Jika L = {0, 11} maka L* terdiri dari string-string 0 dan 1 dimana 1 muncul secara berpasangan, e.g., 011, 11110 dan e. Tetapi bukan 01011 atau 101
