MAKALAH TEORI BAHASA DAN AUTOMATA

TEORI BAHASA DAN AUTOMATA

PENGERTIAN BAHASA DAN AUTOMATA

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 abcd adalah sebuah string yang dibangun dari ketiga simbol tersebut.

·         Jika w adalah sebuah string maka panjang string dinyatakan sebagai ?w? dan didefenisikan sebagai cacahan (banyaknya)  simbol yang menyusun string tersebut. Sebagai contoh, jika w=abcd maka ?w?= 4.

·         String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol ? (atau^) sehingga ???= 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.

·         Alphabet adalah himpunan 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 ? adalah semua prefik(x)

·         ProperPrefik string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih symbol-simbolpaling belakang dari string w tersebut. Contoh : ab, a, dan ? adalah semua ProperPrefik(x)

·         Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih symbol-simbol paling depan dari string w tersebut. Contoh : abc, bc, c dan ? adalah semua Postfix(x)

·         ProperPostfix (atau poperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih symbol-simbol paling depan dari string w tersebut. Contoh ; bc, c, dan ? adalah semua ProperPostfix(x)

·          Head string w adalah symbol paling depan dari string w. contoh : a adalah Head(x)

·         Tail string w adlah string yang dihasilkan dari string w dengan menghilangkan symbol 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 symbol-simbol paling depan dan/atau symbol-simbol paling belakang dari string w tersebut. Contoh : abc, ab, bc, a, b, c, dan ? adalah semua Substring(x)

·         ProperSubstring string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih symbol-simbol paling depan dan/atau symbol-simbol paling belakang dari string w tersebut. Contoh : ab, bc, a, b, c, dan ? adalah semua Substring(x)

·         Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih symbol-simbol dari string w tersebut. Contoh : abc, ab, bc, ac, a, b, c, dan ? adalah semua Subsequence(x)

·         ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih symbol-simbol dari string w tersebut. Contoh : ab, bc, ac, a, b, c, dan ? adalah semua Subsequence(x)

·         Concatenation adalah penyambungan dua buah string. Operator concatenation concate atau tanpa lambing 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

·         Kleene Closure : x* = ??x?xx?xxx?... = ??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 : Prefik(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 :

o   Operasi concatenation bersifat asosiatif : x(yz) = (xy)z

o   Elemen identitas operasi concatenation adalah ? : ?x = x? = x

·         Tiga sifat aljabar alternation :

o   Operasi alternation bersifat komutatif : x?y = y?x

o   Operasi alternation bersifat asosiatif : x?(y?z) = (x?y)?z

o   Elemen identitas operasi alternation adalah dirinya sendiri : x?x =x

·         Sifat distributive concatenation terhadap alternation : x (y?z) = xy?xz

·         Beberapa kesamaan :

o   Kesamaan ke-1 : (x*)* = x*

o   Kesamaan ke-2 : ??x = x ?? = x*

o   Kesamaan ke-3 : (x?y)* = ??x?y?xx?yy?xy?yx?... = semua string yang merupakan concatenation dari nol atau lebih x, y, atau keduanya.

Teori Bahasa Automata Dalam Ilmu Komputer

Suatu teori hanya menarik jika dapat membantu dalam mencari solusi terbaik. Tanpa penerapan timbul pertanyaan, mengapa mempelajari teori?

Teori memberikan konsep dan prinsip yang menolong untuk memahami perilaku dari suatu persoalan yang berkorelasi dengan teori tersebut. Bidang ilmu komputer meliputi topik yang luas, dari perancangan mesin sampai pemrograman. Disamping perbedaan yang ada, terdapat keseragaman prinsip-prinsip umum yang dipakai. Untuk mempelajari prinsip-prinsip dasar tersebut, kita mengkonstruksi suatu mesin otomata sebagai model abstrak dari komputer dan komputasi. Model ini memiliki fungsi-fungsi yang penting dan umum pada perangkat keras dan perangkat lunak komputer. Meskipun model tersebut sederhana untuk diterapkan langsung pada dunia nyata, keuntungan yang diperoleh dari mempelajarinya adalah memberikan landasan untuk basis dari suatu pengembangan algoritma. Pendekatan ini, juga diterapkan pada ilmu sains lainnya.

			Logika dasar persoalan

 

           

 

 

Automata Berhingga

Automata adalah suatu mesin sekuensial (otomatis), yang menerima input (dari pita masukan ) dan mengeluarkan output, keduanya dalam bentuk diskrit. Teori automata khususnya Finite State Automata (FSA) dapat digunakan untuk memodelkan pemecahan masalah / solusi dari permasalahan-permasalahan dari aplikasi yang berbasis kecerdasan buatan. Kelebihan pemodelan menggunakan FSA ini dibandingkan dengan pemakaian pohon keputusan adalah struktur yang lebih sederhana jika terdapat beberapa state / keadaan yag muncul berulang kali.

Otomata adalah sebuah 5 tupel:         

·         Q adalah himpunan berhingga dari state,

·         Σ adalah himpunan simbol-simbol,

·         δ adalah fungsi transisi,

·          adalah simbol awal, adalah state akhir.

Automata berhingga adalah automata dengan masukan yang berhingga atau tidak tak terbatas. Dengan melakukan pemisalan bahwa untuk suatu himpunan tidak kosong • , maka • * adalah himpunan seluruh deret dari panjang berhingga anggota • , termasuk deret kosong • .

Otomata hingga melibatkan stata dan transisi antar stata yang merupakan tanggapan atas masukan. Otomata hingga berguna untuk merekayasa perangkat lunak-perangkat lunak tertentu termasuk komponen lexical analyzer yang terdapat pada compiler dan sistem pemeriksa kebenaran pada sirkuit atau protocol.

Otomata merupakan suatu system yang terdiri dari sejumlah berhingga state, dimana state menyatakan informasi mengenai input yang lalu dan dapat pula dianggap sebagai memori mesin. Mesin otomata akan membuat keputusan yang akan menindikasikan apakah input itu diterima atu tidak. Teori bahasa dan otomata merupakan komponen utama dalam dan gagsan mendasar dari komputasi. Didalam otomata dikenal adanya Finite State Automata. Finite State Automata bukanlah suatu mesin fisik, tetapi merupakan suatu model matematika dari suatu system yang menerima input dan output diskrit. Finite State Automata merupakan mesin otomata dari bahasa regular. suatu Finite State Automata mempunyai state yang banyaknya tak berhingga dan dapat berpindah-pindah dari suatu state ke state lain.

Automata merupakan suatu studi abstrak yang terdiri dari suatu himpunan tiga tupel yaitu M={S, S, D} dimana S menyatakan state (keadaan); S menyatakan input; dan D menyatakan penentuan keadaan nilai. Subjek utama dalam tulisan ini adalah mesin sekuensial, sebuah struktur penting yang menjadi dasar dari pirantipiranti, aktivitas, dan proses pengambilan keputusan, terutama yang berhubungan dengan komputer.        

Automata merupakan suatu sub struktur utama dari mesin atau proses sekuensial tersebut. Pada mesin sekuensial, suatu proses dibangkitkan oleh masukan tertentu dan menghasilkan keluaran tertentu pula berdasarkan informasi yang dimiliki.

Automata merupakan struktur transisi dari suatu mesin sekuensial, dengan demikian pada dasarnya automata adalah bagian dari suatu mesin sekuensial dengan struktur keluaran yang telah dihapus.

Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu Pemodelan geografis berbasiskan Cellular Automata (CA) dan Multi Agent System (MAS) memiliki kekurangan:

·         Pada Cellular Automata, automata secara individual dapat menyebarkan informasi, tapi tidak bebas bergerak

·         Pada Multi Agent System, automata bergerak secara bebas dan mandiri, tetapi mengabaikan sifat-sifat ruang (space) dan keruangan (spasial).

Cellular Automata

Automata merupakan bentuk jamak dari automaton. Automaton adalah suatu mekanisme pemrosesan secara diskrit, berdasarkan keadaan internal dari suatu obyek. Dalam automata, obyek (sel atau agent) memiliki keadaan dan aturan yang menentukan perubahan.

Berikut sifat-sifat dari Automata:

·         Berganti keadaan menurut waktu

·         Sesuai seperangkat aturan

·         Berdasarkan keadaan internal dan eksternal

·         Dalam langkah yang berurutan.

Ekspresi Reguler

Exspresi regular merupakan notasi structural untuk mendeskripsikan pola-pola yang sama dan dapat diwakili oleh otomata hingga. Exspresi regular digunakan pada berbagai tipe perangkat lunak yang biasa kita gunakan, termasuk perangkat lunak untuk mencari pola-pola dalam texs atau nama file.

Tata Bahasa Bebas-Konteks

Tata bahasa bebas konteks ini merupakan notasi penting yang digunakan untuk mendeskripsikan sruktur bahasa pemograman dan himpunan-himpunan untai yang berhubungan; digunakan untuk membuat komponen parser pada compiler.

Mesin Turing

Mesin turing adalah otomata yang menjadi model computer yang kita kenal saat ini. Mesin turing memungkinkan kita untuk mempelajari decidability, yaitu pertanyaan mengenai apa yang dapat dan tidak dapat dikerjakan oleh computer. mesin ini juga memungkinkan kita menbedakan tractable problem (dapat dipecahkan dalam waktu polynomial) dari intractable problem (tidak dapat dipecahkan dalam waktu polynomial).

Pembuktian Deduktif

Metode pembuktian yang mendasar ini dilakukan dengan cara mendaftar stateman yang diketahui benar atau yang secara logika mengikuti beberapa statemen sebelumnya.

Pembuktian stetemen jika-maka

Banyak teorema memiliki bentuk “jika (sesuatu) maka (sesuatu yang lain)”. Stateman tersebut atau stateman yang mengikuti “jika” merupakan hipotesis dan yang mengikuti “maka” adalah kesimpulan. Pembuktian deduktif statemen jika-maka dimulai dengan hipotesis dan dilanjutkan dengan statemen yang mengikuti secara logika hipotesis dan statemen sebelumnya, hingga kesimpulan dibuktikan sebagai salah satu statemen.

 Pembuktian stateman jika dan hanya jika

Ada teorima-teorema yang memiliki bentuk “(sesuatu) jika dan hanya jika (sesuatu yang lain)”. Statemen-statemen tersebut dibuktikan dengan cara statemen “jika-maka” pada kedua arah. Jenis teorema yang sama mengklain kasamaan himpunan-himpunan yang dideskripsikan dengan dua cara yang berbeda;

Pembuktian Kontrapositif

Pembuktian kontrapositif kadang kala,  lebih mudah untuk membuktikan statemen “jika H maka C” dengan membuktikan “jika hal dan bukan C maka (sesuatu yang diketahui salah).” Pembuktian dengan cara ini disebut sebagai pembuktian dengan kontradiksi.

Counter example:

Tidak jarang kita diminta untuk menunjukan bahwa suatu statemen tertentu tidak benar. jika statemen memiliki satu atau lebih para meter, makakita dapat menunjukan bahwa statemen tersebut salah sebagai suatu generalisasi dengan menyediakan satu saja counterexample, yaitu suatu penetapan/penyerahan nilai kepada parameter yang membuat statemen tersebut salah.

Pembuktuan Induktif

Statemen yang memiliki parameter bilangan bulat n sering kali dapat dibuktikan dengan induksi pada n. kita membuktikan statemen tersebut benar atau basis, yaitu sejumblah berhingga kasus untuk nilai n tertentu dan kemudian membuktikan langkah induktif: bahwa jika statemen bernilai benar untuk nilai-nilai hingga n, maka ia juga bernilai benar untuk n + 1.

Intruksi Struktural

Pada beberapa situasi, teorema yang akan dibuktika secara induktif teorema mengenai suatu kontruksi yang didefinisikan secara rekursif , misalnya pohon (tree). Kita dapat membuktikan teorema mengenai obyek-obyek yang dikontruksi melalui induksi pada jumblah langkah yang digunakan untuk mengkontruksinya. Jenis intruksi ini dirujuk sebagai structural.

Alfabet

Alphabet adalah sembarang himpunan simbul-simbul.

Untai (string):

Untai adalah deretan simbul-simbul yang panjangnya berhingga.

Bahasa dan Problema

Bahasa adalah himpunan (bisa jadi himpunan tak hingga) untai-untai, seluruhnya memilih timbulnya dari satu alphabet yang sama. Ketika suatu untai bahasa ditafsirkan denggan suatu cara pertanyaan mengenai apakah untai tersebut berada dibahasanya sering disebut sebagai problema.

Jenis-jenis Otomata Berhingga

1.    Otomata Berhingga Deterministik

Otomata berhingga deterministik (DFA - Deterministic Finite Automata) adalah sebuah otomata yang fungsi transisinya adalah:

2.    Otomata Berhingga Non-Deterministik

Otomata berhingga non-deterministik (NFA - Nondeterministic Finite Automata) berbeda dengan DFA dalam hal fungsi transisinya:

Fungsi transisi dalam NFA memetakan pasangan Q dan Σ kepada himpunan kuasa dari Q. Fungsi transisi yang didefinisikan seperti ini memungkinkan suatu simbol masukan untuk mengakibatkan transisi dari sebuah state ke beberapa kemungkinan state yang lain.

3.    Otomata Pushdown

Otomata Pushdown adalah salah satu varian otomata dengan 7-tupel di mana:

·         Q adalah himpunan berhingga dari state,

·         Σ adalah himpunan simbol-simbol,

·         adalah simbol awal

·         adalah state akhir

Dalam mesin sekuensial terdiri dari dua buah struktur utama yakni struktur transisi dan struktur keluaran. Struktur transisi meliputi keadaan, keluaran, dan fungsi keluaran. Karena struktur keluaran merupakan bagian eksternal dari mesin, maka lebih menarik untuk penerapan praktis dibandingkan dengan struktur transisi yang merupakan bagian internal.    

Struktur keluaran tergantung pada struktur transisi sehingga tidak dapat saling dipisahkan, sedangkan struktuer transisi dari suatu mesin sekuensial tidak tergantung pada struktur keluaran dan dapat diuji secara terpisah.

CONTOH-CONTOH SOAL

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

q0 q1 q2 b

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.

1.                  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.

2.                  Tentukan bahasa dari grammar berikut :

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)

?

? a Aa (2)

?a ba (3)

Dari pola kedua kalimat disimpulkan : L (G) = { a ba ? n ? 1 }

3.                  Tentukan grammar  bebas konteks untuk bahasa

L (G) = {a b ?n,m ? 1, n ? m}

Jawab :

Langkah kunci : sulit untuk mendefenisikan L (G) secara langsung. Jalan keluarnya adalah dengan mengingat bahwa x ? y berarti x > y atau x < y.

L = L ? L, L = {a b ?n > m? 1}, L = {a b ?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}

4.                   Tentukan sebuah grammar bebas konteks untuk bahasa :

L = bilangan bulat non negative 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}

5.                  Tentukan sebuah grammar bebas konteks untuk bahasa :

L₅  = bilangan bulat non negative 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 g N │GA│JA, A g N│NA│JA, Gg2│4│6│8,

Ng 0 │2│4│6│8, J g 1│3│5│7│9}