Diskrit, Kontinue dan Komputasi pada Teori Bahasa Otomata

Belang Telon | Pada bab-bab awal materi Teori Bahasa Otomata (TBO) terdapat beberapa istilah yang tidak hanya ditemukan dalam materi teori bahasa otomata tetapi juga dalam materi matakuliah yang lain. Beberapa istilah tersebut adalah diskrit, kontinue dan komputasi.

Diskrit adalah Istilah yang digunakan untuk menyatakan sebuah data yang dapat dinyatakan dalam bentuk angka, di mana data tersebut dapat dinyatakan dalam jumlah yang pasti (Countable / berhingga). Ada juga yang menyatakan suatu benda dapat dikatakan diskrit jika ia terdiri dari elemen-elemen yang tersusun dan berbeda dengan elemen-elemen lain yang tidak bersambungan/berkaitan.
Kontinu adalah istilah yang digunakan untuk menyatakan sebuah data yang dapat dinyatakan dalam bentuk angka, di mana data tersebut dapat dinyatakan dalam jumlah yang tidak pasti (UnCountable / tidak berhingga).
Komputasi 
Komputasi bisa diartikan sebagai cara untuk menemukan pemecahan masalah dari data input dengan menggunakan suatu algoritma. Komputasi menjadi isu penting karena mempelajari bagaimana kita dapat merancang mesin yang mampu melakukan proses-proses intelektual (yang mulanya hanya dapat dilakukan manusia). Namun dalam merancang seringkali kita terkendala dengan berbagai macam batasan.

Tetapi apakah benar jika batasan-batasan (yang dimiliki komputer) pada dasarnya disebabkan oleh kelemahan programmer (manusia)??? bukan batasan intrinsik yang dimiliki mesin/komputer ?! Jika Ya, maka kita berharap agar batasan-batasan tersebut dapat terreduksi melalui pengembangan teori komputasi.

Teknik komputasi
Perangkat ilmu tentang alat (biasanya sebuah komputer), metode (yang disebut algoritma) dan teori (bukti matematis bahwa komputasi memberi hasil yang benar) yang diperlukan untuk melaksanakan komputasi tersebut.  Sementara itu dalam melakukan kegiatan komputasi untuk menyelesaikan suatu persoalan, seorang teknisi harus memperhatikan interaksi dari alat (komputer yang digunakan), metode (yaitu program yang dimiliki), dan sifat unik dari soal yang dihadapi, sebab dalam praktek soal-soal memiliki tingkat kesulitan yang berbeda-beda:  ada soal yang relatif sangat gampang, ada yang sulit, tetapi juga ada soal yang sangat sulit.

Contoh hal / proses yang dapat dikomputasikan:
•    Digunakan sebagai pemecahan kasus pada bidang ilmu Fisika secara sederhana
•    Sebagai Tomografi yang berbentuk analitik dari 2-D mapping
•    Menghitung suatu persamaan
•    Membantu memecahkan suatu masalah
•    Scanning
•    Sistem pakar
•    Membuat grafik 3D
•    Kecerdasan buatan
•    Perhitungan numerik
•    Games
•    Algoritma
•    Formula
•    Persamaan Linier
•    Persamaan Kuadrat
•    Persamaan Pangkat Tiga
•    Bilangan
•    Operasi Matematika
•    Data
•    Informasi
•    Character

Model Komputasi Awal :

 

Model Komputasi Sekarang : 

Sebagai contoh proses komputasi untuk : f(x)  =  x  +  x  +  x

Langkah 1:

Langkah 2:

Langkah 3:

 

Langkah 4: 

Diskrit, Kontinue dan Komputasi pada Teori Bahasa Otomata

BelangTelon | Diskrit adalah Istilah yang digunakan untuk menyatakan sebuah data yang dapat dinyatakan dalam bentuk angka, di mana data tersebut dapat dinyatakan dalam jumlah yang pasti (Countable / berhingga). Ada juga yang menyatakan suatu benda dapat dikatakan diskrit jika ia terdiri dari elemen-elemen yang tersusun dan berbeda dengan elemen-elemen lain yang tidak bersambungan/berkaitan.
Kontinu adalah istilah yang digunakan untuk menyatakan sebuah data yang dapat dinyatakan dalam bentuk angka, di mana data tersebut dapat dinyatakan dalam jumlah yang tidak pasti (UnCountable / tidak berhingga).

Komputasi  
Komputasi bisa diartikan sebagai cara untuk menemukan pemecahan masalah dari data input dengan menggunakan suatu algoritma. Komputasi menjadi isu penting karena mempelajari bagaimana kita dapat merancang mesin yang mampu melakukan proses-proses intelektual (yang mulanya hanya dapat dilakukan manusia). Namun dalam merancang seringkali kita terkendala dengan berbagai macam batasan. Tetapi apakah benar jika batasan-batasan (yang dimiliki komputer) pada dasarnya disebabkan oleh kelemahan programmer (manusia)???

bukan batasan intrinsik yang dimiliki mesin/komputer ?! Jika Ya, maka kita berharap agar batasan-batasan tersebut dapat terreduksi melalui pengembangan teori komputasi.

Teknik Komputasi
Perangkat ilmu tentang alat (biasanya sebuah komputer), metode (yang disebut algoritma) dan teori (bukti matematis bahwa komputasi memberi hasil yang benar) yang diperlukan untuk melaksanakan komputasi tersebut.  Sementara itu dalam melakukan kegiatan komputasi untuk menyelesaikan suatu persoalan, seorang teknisi harus memperhatikan interaksi dari alat (komputer yang digunakan), metode (yaitu program yang dimiliki), dan sifat unik dari soal yang dihadapi, sebab dalam praktek soal-soal memiliki tingkat kesulitan yang berbeda-beda:  ada soal yang relatif sangat gampang, ada yang sulit, tetapi juga ada soal yang sangat sulit.

Model komputasi awal :

Model komputasi sekarang :

Contoh hal / proses yang dapat dikomputasikan:
•    Digunakan sebagai pemecahan kasus pada bidang ilmu Fisika secara sederhana
•    Sebagai Tomografi yang berbentuk analitik dari 2-D mapping
•    Menghitung suatu persamaan
•    Membantu memecahkan suatu masalah
•    Scanning
•    Sistem pakar
•    Membuat grafik 3D
•    Kecerdasan buatan
•    Perhitungan numerik
•    Games
•    Algoritma
•    Formula
•    Persamaan Linier
•    Persamaan Kuadrat
•    Persamaan Pangkat Tiga
•    Bilangan
•    Operasi Matematika
•    Data
•    Informasi
•    Character

Grammar pada Teori Bahasa Otomata

Grammar Klas 0 :
Unrestricted Grammar : Aturan-aturan sintaktik (productions) yang digunakan untuk membentuk kalimat tidak mempunyai batasan yang jelas.
Contoh :
G = ({S, A, B, C, D}, {a, b}, S, q), dengan q adalah :
S ® CD Aa ® aA C ® e
C ® aCA | bCB Ab ® bA D ® e
AD ® aD Ba ® aB
BD ® bD Bb ® bB
Bahasa yang didefinisikan grammar di atas adalah :
L(G) = { ww | w Î {a, b}}
Grammar Klas 2 :
Context-Free Grammar (CFG) : Grammar dengan production yang berbentuk a ® b, dimana |a| £ |b| dengan a Î Vn dan |a| = 1. Dengan demikian, production-production pada klas grammar ini hanya memiliki satu non-terminal di sisi kiri setiap productionnya. Bahasa yang didefinisikan oleh CFG ini disebut Context-Free Language.
CFG merupakan satu-satunya klas grammar yang telah memiliki algoritma parsing yang optimal. Sehingga hampir semua bahasa pemrograman menggunakan CFG untuk mendefinifikan aturan-aturan sintaktik bahasanya.
Contoh : Bahasa = { an b an | n ³ 1 } didefinisikan melalui grammar berikut :
S ® aCa
C ® aCa | b
Derivasi untuk input string a3 b a3 adalah sebagai berikut :
S Þ aCa Þ aaCaa Þ aaaCaaa Þ aaabaaa
Grammar Klas 3 :
Regular Grammar : Grammar dengan production yang berbentuk a ® b, dimana |a| £ |b| dengan a Î Vn dan |a| = 1. Sedangkan b mempunyai bentuk aB atau a (a Î VT dan B Î VN). Bahasa yang didefinisikan oleh Regular Grammar ini disebut Regular Language.
Bahasa pemrograman yang menggunakan aturan sintaktik bahasa regular ini antara lain adalah javascript, perl, dll.
Contoh : Bahasa = { an b am | n ³ 1 } didefinisikan melalui grammar berikut :
S ® aS | aB
C ® aC | a
B ® bC
Derivasi untuk input string a3 b a2 adalah sebagai berikut :
S Þ aS Þ aaS Þ aaaB Þ aaabC Þ aaabaC Þ aaabaa