Teori Bahasa dan Automata

Nama : M. Danar Mahendra

NPM : 011170043

Prodi : Teknik Informatika

1. Teori Bahasa dari Sudut Pandang Linguistik dan Komputasi

Linguistik :

Bahasa adalah alat yg digunakan oleh manusia utk berkomunikasi.
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 bahasa berbeda
Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya.
Bahasa natural/manusia bersifat sebaliknya, yaitu grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat.
Bahasa dalam bentuk tulisan terdiri atas simbol-simbol satuan yang jika dikombinasikan akan mempunyai arti yang berbeda.
Simbol-simbol yang biasa digunakan dalam sebuah bahasa terbatas jumlahnya, yang membentuk sebuah himpunan dan disebut sebagai abjad/alphabet.

Komputasi :

Bidang antardisiplin yang mengkaji permodelan bahasa alami dengan statistika dan berbasis aturan dari sudut pandang komputasi.
Salah satu bidang komputer sains yang berfokus pada interaksi antara manusia dengan komputer melalui bahasa alami.
Bahasa komputasi dapat digolongkan menurut media penyimpanan dari bahasa, baik itu bahasa lisan ataupun tulisan.
Selain itu, juga dapat digolongkan menurut pekerjaan yang dilakukan, baik menganalisis bahasa (recognition) atau pembuatan bahasa artifisial (generation).

2. Pengertian Automata dan Kegunaannya

Definisi Automata :

Mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Teori Automata adalah teori tentang mesin abstrak yang bekerja secara sekuensial yang menerima dan mengeluarkan output dalam bentuk diskrit. Automata juga merupakan sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yang lalu dan dapat dianggap sebagai memori mesin. Di akhir, input pada mesin automata dianggap sebagai bahasa yang harus dikenali oleh mesin, dan selanjutnya mesin automata membuat

Kegunaan Automata :

Secara garis besar, fungsi Automata ada dua :

a. Fungsi Automata sebagai pengenal (Recognizer) dari string-string sebuah bahasa. Dalam hal ini, bahasa sebagai masukan dari automata.

b. Fungsi Automata sebagai pembangkit (Generator) dari string-string dari suatu bahasa. Dalam hal ini, bahasa sebagai keluaran dari automata.

3. Himpunan, Relasi dan Fungsi

Himpunan

Sebuah kumpulan benda atau objek yang dapat didefinisikan dengan jelas. Benda atau objek dalam himpunan disebut elemen atau atau anggota himpunan. Sehingga dapat ditarik kesimpulan bahwa objek pada sebuah himpunan harus didefinisikan dengan jelas, agar supaya dapat dibedakan atau ditentukan antara benda / objek yang termuat dan yang tidak termuat pada himpunan.

Jenis-Jenis Himpunan

1. Himpunan Bagian (Subset) : Anggota semua himpunan yang menjadi anggota himpunan lain.

" ⊂ " : himpunan bagian
" ⊄ " : bukan himpunan bagian
Himpunan A dikatakan himpunan bagian dari himpunan B jika dan hanya jika setiap elemenA merupakan elemen dari B.
Dalam hal ini, B dikatakan superset dari A.
Notasi: A ⊂ B

2. Himpunan Kosong : Himpunan yang tidak memiliki anggota, dinyatakan dalam {} atau ∅.

Himpunan {{ }} dapat juga ditulis sebagai {∅}
Himpunan {{ }, {{ }}} dapat juga ditulis sebagai {∅, {∅}}
{∅} bukan himpunan kosong karena ia memuat satu elemen yaitu himpunan kosong.

3. Himpunan Semesta : Semua anggota yang sedang dibicarakan.

4. Himpunan yang Sama

A = B jika dan hanya jika setiap elemen Amerupakan elemen B dan sebaliknya setiap elemenB merupakan elemen A.
A = B jika A adalah himpunan bagian dari Bdan B adalah himpunan bagian dari A. Jika tidak demikian, maka A ¹ B.
Notasi : A = B « A ⊂ Bdan B ⊂ A

5. Himpunan yang Ekuivalen

Himpunan A dikatakan ekivalen dengan himpunan B jika dan hanya jika kardinal dari kedua himpunan tersebut sama.
Notasi : A ~ B « |A| =|B|

6. Himpunan Saling Lepas

Dua himpunan A dan B dikatakan saling lepas (disjoint) jika keduanya tidak memiliki elemen yang sama.
Notasi : A // B

7. Himpunan Kuasa

Himpunan kuasa (power set) dari himpunan Aadalah suatu himpunan yang elemennya merupakan semua himpunan bagian dari A, termasuk himpunan kosong dan himpunan Asendiri.
Notasi : P(A) atau 2A.
Jika |A| = m, maka P(A)| = 2m.

Relasi

Relasi, menurut KBBI (Kamus Besar Bahasa Indonesia) dapat diartikan sebagai hubungan, perhubungan, pertalian, atau pelayanan.

Sedangkan dalam dunia matematika, relasi memiliki pengertian sebagi himpunan bagian antara A dan B atau relasi yang memasangkan setiap elemen yang ada pada himpunan A secara tunggal, dengan elemen yang ada pada B.

Fungsi dari Relasi itu sendiri, salah satunya sebagai pemetaan setiap anggota sebuah himpunan kepada anggota himpunan yang lain.

Contoh :

Jika diketahui himpunan A = {Eko, Rina, Tono, Dika}; B = {Merah, Hitam, Biru}, maka relasi “suka dengan warna” himpunan A ke himpunan B dapat disajikan dalam Diagram panah, Diagram Cartesius, dan Himpunan Pasangan Berurutan.

a. Diagram panah

b. Diagram Cartesius

c. Himpunan Pasangan Berurutan

R = {(Eko, Merah), (Rina, Hitam), (Tono, Merah), (Dika, Biru)}

Fungsi

Fungsi atau yang sering disebut juga dengan pemetaan masih termasuk dalam relasi. Suatu relasi disebut fungsi jika semua anggota himpunan daerah asal dipasangkan tepat satu ke daerah kawannya.
Simbol fungsi yang memetakan himpunan A ke B adalah

Perhatikan diagram-diagram panah di bawah ini !

Keterangan:

Relasi f adalah fungsi, karena setiap anggota A mempunyai pasangan tepat satu dengan anggota B
Relasi g adalah fungsi, karena setiap anggota A mempunyai pasangan tepat satu dengan anggota B, meski peta semua anggota A sama.
Relasi h adalah fungsi, karena setiap anggota A mempunyai pasangan tepat satu dengan anggota B, meski terdapat anggota B yang tidak memiliki prapeta di A
Relasi i bukan fungsi, karena terdapat anggota A yang memiliki peta di B lebih dari satu.
Relasi j bukan fungsi, karena ada anggota A yang tidak memiliki peta di B

Semua fungsi adalah relasi, tapi tidak semua relasi adalah fungsi

Relasi R:A→B dikatakan fungsi apabila setiap anggota A memiliki pasangan tepat satu di B. Artinya:

Semua anggota A harus memiliki peta di B.
Semua anggota A memiliki peta di B hanya satu, tidak boleh lebih.
Anggota B boleh ada yang tidak memiliki pasangan, tetapi tidak semua.
Anggota B boleh memiliki prapeta lebih dari satu.

Sifat-sifat Fungsi

Fungsi dikelompokkan menjadi 3 (tiga) jenis yaitu :

Fungsi Injektif/Fungsi Into (Fungsi Satu-satu)
Fungsi Surjektif (Fungsi Onto)
Fungsi Bijektif (Korespondensi Satu-satu)

Pengelompokkan tersebut didasarkan pada sifatnya. Perbedaan ketiga jenis tersebut dapat disimak pada penjelasan di bawah.

Fungsi pertama yang akan dibahas adalah Fungsi Injektif atau sering disebut dengan Fungsi Into atau Fungsi Satu-Satu. Fungsi

dikatakan fungsi injektif jika dan hanya jika anggota kodomain hanya dipasangkan satu kali dengan anggota domain.

Pada fungsi injektif, anggota himpunan daerah kodomain boleh tidak memiliki pasangan, namun semua anggota kodomain yang terpsangkan hanya ada satu, tidak boleh ada yang lebih dari satu.

Perhatikan gambar di bawah untuk melihat lebih detail mengenai perbedaannya !

Fungsi Surjekti (Onto) memiliki ciri yaitu anggota kodomainnya boleh memiliki pasangan lebih dari satu, namun tidak boleh ada anggota kodomain yang tidak dipasangkan. Fungsi surjektif biasanya dipenuhi apabila jumlah anggota kodomain sama atau lebih banyak dari anggota domain.

Perhatikan gambar di bawah untuk menambah pemahan sobat idschool tentang sifat fungsi surjektif !

Fungsi Bijektif merupakan gabungan dari fungsi injektif dan surjektif. Pada fungsi bijektif, semua anggota domain dan kodomain terpasangkan tepat satu. Kebalikan fungsi dari fungsi injektif dan surjektif belum pasti fungsi/pemetaan, namun kebalikan fungsi dari fungsi bijektif juga merupakan fungsi/pemetaan. Perhatikan gambar di bawah !

4. Simbol, Abjad dan String

Simbol

Pengertian simbol adalah suatu tanda yang bisa mengantarkan seseorang kedalam gagasan masa depan maupun masa lalu. Berdasarkan bahasa Yunani, Simbol berasal dari kata symballo yang berarti melempar secara bersamaan, melempar ataupun meletakkan secara bersama-sama dalam sebuah ide atau gagasan dari objek yang terlihat sehingga objek tersebut dapat mewakili suatu gagasan yang ditunjukkan oleh simbol itu sendiri. Simbol ini bisa merujuk pada masa lalu maupun masa depan yang ditunjukkan.

Dalam sejarah pemikiran, simbol memiliki dua pengertian yang sangat berbeda. Dalam pemikiran dan praktik keagamaan, simbol lazim dianggap sebagai pancaran Realitas Transenden. Dalam sistem pemikiran logika dan ilmiah, lazimnya istilah simbol dipakai dalam arti tanda abstrak.

Dalam beberapa pengertian, simbol diartikan sebagai berikut :

Simbol adalah sesuatu yang biasanya merupakan tanda yang terlihat yang menggantikan gagasan atau objek,
Simbol adalah kata, tanda, atau isyarat, yang digunakan untuk mewakili sesuatu yang lain seperti arti, kualitas, abstraksi, gagasan, dan objek,
Simbol adalah apapun yang diberikan arti dengan persetujuan umum dan atau dengan kesepakatan atau kebiasaan,
Simbol sering diartikan secara terbatas sebagai tanda konvensional, sesuatu yang dibangun oleh masyarakat atau individu dengan arti tertentu yang kurang lebih standar dan disepakati atau dipakai anggota masyarakat itu sendiri. Arti simbol dalam konteks ini sering dilawankan dengan tanda ilmiah.

Contoh Simbol-Simbol Keagamaan

Abjad

Abjad memiliki 2 arti. Abjad adalah sebuah homonim karena arti-artinya memiliki ejaan dan pelafalan yang sama tetapi maknanya berbeda. Abjad memiliki arti dalam kelas nomina atau kata benda sehingga abjad dapat menyatakan nama dari seseorang, tempat, atau semua benda dan segala yang dibendakan.

Dalam penggunaan bahasa Indonesia, namun, istilah abjad juga bisa merujuk kepada huruf Alfabet. Masing-masing huruf menggambarkan satu bunyi atau lebih, contoh huruf e dapat menggambarkan bunyi e dalam kata bebek, e dalam kata senang atau e dalam kata tega. Urutan abjad merupakan rangkaian huruf dari A hingga Z, terdiri dari 26 huruf.

Pembagian Huruf

Dalam tata bahasa indonesia yang baik dan benar,huruf dibagi menjadi dua macam yakni huruf vokal (huruf hidup) dan huruf konsonan (huruf mati).

1. Huruf vokal (Huruf hidup)

Yang termasuk huruf hidup atau vokal adalah a, i, u, e, o. Namun,dalam bahasa indonesia kita juga mengenal adanya huruf vokal rangkap (diftong). Adapun huruf vokal rangkap yang sering dipergunakan dalam penggunaan kata adalah ai, au, oi. Ketiga huruf diftong tersebut, biasanya dilafalkan sebagai huruf vokal yang diikuti oleh bunyi luncuran konsonan W dan Y.

Sebagai contoh :

au pada kata surau-kemarau-saudara.

ai pada kata santai-gulai-damai.

oi pada kata amboi-asoi-sepoi.

2. Huruf konsonan (Huruf mati)

Yang termasuk kedalam huruf konsonan (huruf mati) adalah B, C, D, F, G, H, J, K, KH ,L ,M ,N ,N Y, N, G ,P, Q, R, S, SH,SY, T, V, W, X, Y, Z.

String

String, dalam bahasa pemrograman komputer, adalah deretan simbol. Tipe data String adalah tipe data yang digunakan untuk menyimpan barisan karakter.

Tipe-tipe Bahasa String dalam Bahasa Pemrograman :

Bahasa Pascal
Bahasa C
Bahasa C++
Bahasa PHP

1. Bahasa Pascal

Dalam bahasa Pascal, tipe data String dituliskan sebagai String. Pada kompilator Pascal lama, string terpanjang yang dapat dibuat terdiri dari 255 karakter. Hal ini terjadi karena Pascal menggunakan 1 byte data untuk menyimpan panjang efektif string.
Contoh kode Pascal yang menggunakan tipe data string :

program str;
var s: string[100];  //jika panjang maksimum tidak dimasukkan, kompilator akan menganggapnya 255
begining
  su:= 'Hello world';
  writeln(su);
end.

Pada kompilator Pascal yang lebih baru dikenal pula tipe data ANSI-string yang dapat menyimpan karakter lebih banyak.

2. Bahasa C

Dalam bahasa C tidak ada tipe data khusus untuk menyimpan string. String biasanya disimpan sebagai larik dari karakter-karakter. Berbeda dengan bahasa Pascal, string pada bahasa C merupakan sebuah null-terminated string, sehingga kapasitasnya hanya dibatasi oleh kapasitas memori komputer. Seperti pada tipe data larik pada bahasa C, pengguna dapat memberikan batas maksimum karakter yang dapat ditampung.
Contoh kode C yang menggunakan tipe data string :

#include <stdio.h>
int main(){
  char s[100]; /* membuat string dengan panjang maksimum 99 karakter, karena karakter terakhir harus null */
  s = "Hello world";
  printf("%s\n", s);
}

3. Bahasa C++

Bahasa C++ merupakan turunan dari bahasa C sehingga representasi string sebagai larik karakter masih berlaku. Namun bahasa C++ juga menyediakan tipe data string yang terdapat dalam C++ Standard Template Library (STL).
Contoh kode C++ yang menggunakan tipe data string pada STL:

#include <string>
#include <iostream>
using namespace std;
int main(){
  string s;  //panjang maksimum tidak perlu didefinisikan
  s = "Hello world";
  cout<<s<<endl;
}

4. Bahasa PHP

Di PHP String adalah kumpulan dari karakter, bilangan, spasi, dan yang lainnya yang berada dalam tanda petik. Di bawah ini semuanya adalah string :

'9 Januari 2009 '
'1.000.000'
"satu juta"
'Belajar PHP'

Contoh Penggunaan String di PHP :

//mendefinisikan string
$kegiatan = 'Belajar PHP';
$tempat = 'wikipedia';
//Strings Concatenation
echo $kegiatan." di ".$tempat;

Cari Blog Ini

TEKNIK INFORMATIKA