Wednesday 8 February 2012

Peradaban Islam adalah perintis dalam bidang teknologi automata






Peradaban Islam di era keemasan telah menguasai teknologi yang sangat tinggi. Pada abad ke-13 M, dunia Islam sudah menggenggam teknologi robot. Insinyur Muslim di zaman kekhalifahan sudah mampu menciptakan robot mirip manusia. Pencapaian itu sekaligus mematahkahkan klaim Barat yang kerap menyebut Leonardo da Vinci sebagai perintis 


Da Vinci baru merancang pembuatan robot pada 1478, itu pun baru berbentuk desain di atas kertas. Sedangkan, insinyur Muslim yang sangat brilian, Al-Jazari, sudah berhasil merancang dan menciptakan aneka bentuk robot pada awal abad ke-13 M. Atas dasar itulah, masyarakat sains modern menjulukinya sebagai ''Bapak Robot''. Peradaban Islam lebih maju tiga abad dalam teknologi robot dibanding Barat.


Peradaban Islam adalah perintis dalam bidang teknologi automata, yakni sebuah mesin yang dapat berjalan sendiri (self operating). Automata sering digunakan untuk menggambarkan sebuah robot atau lebih khusus robot autonomous. Kata Automata berasal dari bahasa Yunani automatos, yakni berlaku atas kehendak sendiri, bergerak sendiri.


Kata itu digunakan untuk menggambarkan mesin-mesin bergerak tak-elektronik, khususnya yang dirancang untuk menyerupai gerakan manusia atau hewan. Mesin robot yang diciptakan Al-Jazari berbentuk sebuah perahu yang terapung di sebuah danau yang ditumpangi empat robot pemain musik.


Robot yang terdiri atas dua penabuh drum, seorang peniup harpa, dan pemain suling logam itu diciptakan untuk menghibur para tamu kerajaan dalam acara jamuan minum. Al-Jazari mengembangkan prinsip hidrolik untuk menggerakkan mesin yang di kemudian hari dikenal sebagai mesin robot. ''Itu adalah automata pertama yang bisa diprogram,'' ungkap Prof Noel Sharkey.


Robot penabuh drum yang dirakit Al-Jazari dapat memainkan beragam irama yang berbeda-beda. Robot yang ditemukan Al-Jazari itu juga mengundang kekaguman Charles B Fowler. Menurut dia, temuan insinyur Muslim itu bisa disebut ''robot band''. Sebuah pencapaian penting yang belum pernah ditemukan peradaban lain sebelumnya dan kebudayaan lain di zaman itu.


Secara khusus Mark E Rosheim menyimpulkan, kemajuan yang dicapai dunia Islam di era kejayaan dalam bidang robotika sebagai sebuah penemuan lebih maju dibandingkan zaman Yunani. ''Tak seperti desain Yunani, contoh robot yang diciptakan dunia Islam (Arab) mampu mengundang daya tarik. Tak hanya dalam ilusi dramatis, tetapi mampu menghadirkan lingkungan yang bisa membuat manusia lebih nyaman,'' ungkap Rosheim.


Menurut Rosheim, robot ciptaan Al-Jazari itu merupakan salah satu kontribusi peradaban Islam yang sangat penting bagi teknologi. Menurut dia, robot yang diciptakan peradaban Islam di awal abad ke-13 M sudah berbentuk manusia robot dan mampu membantu manusia untuk tujuan praktis. Sayangnya, kata dia, robot itu tak diciptakan untuk kepentingan industri.


Selain ''robot band'', Al-Jazari juga berhasil menciptakan sebuah robot pramusaji berbentuk manusia yang bertugas untuk menghidangkan air, teh, atau minuman lainnya. Minuman disimpan dalam sebuah tank dengan reservoir (penampung air). Dari penampung itu, air dialirkan ke dalam sebuah ember dan setelah tujuh menit mengalir ke sebuah cangkir. Setelah itu, robot itu mengeluarkan minumannya.



Penemuan penting lainnya di era kejayaan Islam yang tak kalah menarik adalah pencuci tangan otomatis dengan mekanisme pengurasan. Mekanisme yang dikembangkan Al-Jazari itu, kini digunakan dalam sistem kerja toilet modern. Robot pencuci tangan otomatis itu berbentuk seorang wanita yang berdiri dengan sebuah baskom berisi air.





       
Ketika seorang pengguna menahan tuas, air akan mengering dan robot wanita itu akan kembali mengisi baskom dengan air. Robot lainnya yang dikembangkan Al-Jazari adalah air mancur burung merak. Robot ini berfungsi sebagai pengganti pembantu atau pelayan. Robot ini memudahkan orang saat membersihkan tangan, karena robot burung merak itu akan menawarkan sabut dan handuk secara otomatis.


Robot lainnya yang diciptakan insinyur Muslim adalah burung merak otomatis yang bisa bergerak. Al-Jazari menggerakkan robot burung merak itu dengan tenaga air. Teknologi robot lainnya yang ditemukan Al-Jazari adalah pintu otomatis sebagai bagian dari salah satu jam air yang diciptakannya.


 

Teknologi automata yang dikembangkan Al-Jazari mencapai 50 jenis dan semuanya ditulis dan digambarkan dalam kitabnya yang sangat legendaris, Al-Jami Bain al-Ilm Wal ‘Aml al-Nafi Fi Sinat ‘at al-Hiyal (The Book of Knowledge of Ingenious Mechanical Devices). Karyanya ini berisi tentang teori dan praktik mekanik. Dalam kitab itu, Al-Jazari membeberkan secara detail beragam hal terkait mekanika.



Selain itu, Al-Jazari juga menciptakan teknologi automata lainnya yang berfungsi untuk membantu dan memudahkan tugas manusia. Ia antara lain menciptakan peralatan rumah tangga dan musik automata yang digerakkan tenaga air.
  

Semua robot yang ditemukan peradaban Islam lewat Al-Jazari sungguh sangat mencengangkan. ''Tak mungkin mengabaikan hasil karya Al-Jazari yang begitu penting. Dalam bukunya, ia begitu detail memaparkan instruksi untuk mendesain, merakit, dan membuat sebuah mesin,'' ungkap sejarawan Inggris, Donald R Hill, dalam tulisannya berjudul, Studies in Medieval Islamic Technology.


Sejarawan lainnya yang terpesona dengan risalah penemuan Al-Jazari adalah Lynn White. ''Jelas sudah bahwa penemu roda gigi pertama adalah Al-Jazari. Barat baru menemukannya pada 1364 M.'' Menurut Lynn, kata gear (roda gigi) baru menjadi perbendaharaan kata atau istilah dalam desain mesin Eropa pada abad ke-16 M.


Dalam pandangan Donald Hill, tak ada satu pun dokumen yang mampu menandingi karya Al-Jazari sampai abad modern ini. Menurut dia, risalah penemuan Al-Jazari begitu kaya akan instruksi mengenai desain, pembuatan, dan perakitan mesin-mesin.


''Al-Jazari tak hanya mampu memadukan teknik-teknik para pendahulunya dari Arab dan non-Arab, tapi juga dia benar-benar seorang insinyur yang kreatif,'' papar Donald Hill yang begitu mengagumi Al-Jazari. Ketertarikannya atas karya sang insinyur Muslim itu, Donal Hill pun terpacu dan terdorong untuk menerjemahkan karya Al-Jazari pada 1974.
 
                 

                   Al-Jazari Pemimpin Para Insinyur Muslim

   


a'is Al-A'mal. Gelar itu ditabalkan para insinyur Muslim di abad ke-13 M kepada Al-Jazari. Tak heran, jika nama lengkap sang insinyur fenomenal itu adalah Al-Shaykh Rais al-Amal Badi al-Zaman Abu al-Izz ibn Ismail ibn al-Razzaz al-Jazari. Sedangkan, titel Badi al-Zaman dan Al-Shaykh yang disandangnya menunjukkan bahwa dia adalah seorang ilmuwan yang unik, tak tertandingi kehebatannya, menguasai ilmu yang tinggi, serta bermartabat.


a'is Al-A'mal. Gelar itu ditabalkan para insinyur Muslim di abad ke-13 M kepada Al-Jazari. Tak heran, jika nama lengkap sang insinyur fenomenal itu adalah Al-Shaykh Rais al-Amal Badi al-Zaman Abu al-Izz ibn Ismail ibn al-Razzaz al-Jazari. Sedangkan, titel Badi al-Zaman dan Al-Shaykh yang disandangnya menunjukkan bahwa dia adalah seorang ilmuwan yang unik, tak tertandingi kehebatannya, menguasai ilmu yang tinggi, serta bermartabat.


Di sanalah Al-Jazari mencurahkan hidupnya sebagai seorang insinyur dengan menciptakan berbagai mesin. Para penjelajah dan pelancong yang tandang ke wilayah itu pada abad ke-12 M, mengagumi kemakmuran yang diraih Dinasti Artukid. Pada saat itu pula, kedamaian dan stabilitas politik dan keamanan begitu terkendali.


Seperti halnya sang ayah, Al-Jazari mengabdikan dirinya pada raja-raja dari Dinasti Urtuq atau Artuqid di Diyar Bakir dari tahun 1174 M sampai 1200 M sebagai ahli teknik. Semasa hidupnya, Al-Jazari mengalami tiga kali suksesi kepemimpinan di Dinasti Artukid, yakni Nur al-Din Muhammad ibn Arslan (570 H - 581 H/1174 M - 1185 M); Qutb al-Din Sukman ibn Muhammad (681 H - 697 H/1185 M - 1200 M); dan Nasir al-Din Mahmud ibn Muhammad (597 H - 619 H/1200 M - 1222 M).


Atas permintaan Nasir al-Din Mahmud, Al-Jazari menuliskan seluruh penemuannya dalam sebuah risalah yang fenomenal. Dalam pengantar risalahnya, Al-Jazari mengungkapkan bahwa dirinya mulai mengabdi pada Dinasti Artuqid pada 570 H/1174 M. Ia risalah penemuannya, setelah 25 tahun bersama menjadi ahli teknik di bawah kepemimpinan tiga raja Dinasti Artuqid.


Berdasarkan informasi itu, dapat disimpulkan, kemungkinan Al-Jazari menulis risalahnya pada 595 H/1198 M, atau dua tahun sebelum Nasir Al-Din didaulat menjadi raja. Menurut naskah Oxford, Al-Jazari merampumgkam risalahnya yang mengguncang dunia teknik modern pada 16 Januari 1206 M.


arya besar Al-jazari itu disempurnakan oleh Muhammad ibn Yusuf ibn `Uthman al-Haskafiat pada akhir Syaban 602 H/10 April 1206. Dari catatan Haskapi, saat itu Al-Jazari sudah tiada. Dari catatan itulah, Al-Jazari diperkirakan wafat pada 602 H/1206 M--beberapa bulan setelah dia menyelesaikan karyanya.      

TEORI 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. Tata bahasa (grammar) adalah kaidah/aturan pembentukan kata/kalimat. Pada pembahasannya, bahasa formal hanya disebut bahasa saja.
Bahasa dalam bentuk tulisan terdiri atas symbol-simbol satuan yang jika dikombinasikan akan mempunyai arti yang berbeda. Simbol-simbol yang biasa dipergunakan dalam sebuah bahasa terbatas jumlahnya, yang membentuk sebuah himpunan dan disebut sebagai abjad/alphabet. Namun kadangkala digunakan istilah karakter yang artinya sama dengan symbol. Deretan dari karakter atau symbol ini membentuk string. Dan himpunan dari semua string yang dibentuk dari suatu abjad ini didefinisikan sebagai bahasa.
Karena bahasa adalah sebuah himpunan dari string, maka untuk mendefinisikan suatu bahasa bisa dilakukan dengan menuliskan semua string yang menjadi anggotanya. Tata Bahasa G = (T,N,S,P), di mana
• T adalah himpunan berhingga simbol-simbol terminal
• N adalah himpunan berhingga simbol-simbol non terminal
• S adalah simbol awal, S ( N
• P adalah himpunan berhingga aturan produksi yang setiap elemennya berbentuk * + ,,
*, , ( (T U N)+, * harus berisi minimal 1 simbol non terminal
Sentential form adalah semua string yang dapat diturunkan dari simbol awal S dengan menggunakan aturan produksi P. Kalimat (sentence) adalah sentential form yang tidak mengandung simbol non terminal. Bahasa yang dihasilkan dari G dinotasikan dengan L(G), yaitu himpunan kalimat yang dapat diturunkan dari S dengan menggunakan P.
AUTOMATA
Automata berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja secara otomatis (mesin). Istilah automata merupakan bentuk tunggal, sedangkan bentuk jamaknya adalah automaton. Teori automata adalah teori tentang mesin abstrak yang bekerja secara sekuensial yang menerima dan mengeluarkan output dalam bentuk diskrit.
Pengertian mesin bukan hanya mesin elektronis/mekanis saja melainkan segala sesuatu (termasuk perangkat lunak) yang memenuhi ketiga ciri di atas. Penggunaan automata pada perangkat lunak terutama pada pembuatan kompiler bahasa pemrograman. Secara garis besar ada dua fungsi automata dalam hubungannya dengan bahasa, yaitu :
· fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini bahasa sebagai masukan dari automata
· fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa, dalam hal ini bahasa sebagai keluaran dari automata
Untuk mengenali string-string dari suatu bahasa, akan dimodelkan sebuah automaton yang memiliki komponen sebagai berikut :
- pita masukan, yang menyimpan string masukan yang akan dikenali;
- kepala pita (tape head), untuk membaca/menulis ke pita masukan;
- Finite State Controller (FSC), yang berisi status-status dan aturan-aturan yang mengatur langkah yang dilakukan oleh automaton berdasarkan status setiap saat dan simbol masukan yang sedang dibaca oleh kepala pita;
- pengingat (memory), untuk tempat penyimpanan dan pemrosesan sementara Automaton pengenal, setelah membaca string masukan dan melakukan langkahlangkah pemrosesan yang diperlukan, akan mengeluarkan keputusan apakah string tersebut dikenali atau tidak.
- Konfigurasi adalah suatu mekanisme untuk menggambarkan keadaan suatu mesin pengenal , yang terdiri atas :
_ status FSC
_ isi pita masukan dan posisi kepala pita
_ isi pengingat
Mesin pengenal bersifat deterministik bila dalam setiap konfigurasi, hanya ada satu kemungkinan yang dapat dilakukan mesin, jika tidak mesin pengenal bersifat nondeterministik.
Sejarah Otomata dan Teori Bahasa
Otomata bermula sebelum komputer ada pada teori di bidang sistem logika matematika atau formal, ilmuwan David Hilbert telah mencoba menciptakan algoritma umum untuk pembuktian (seluruh) persoalan matematika secara otomatis yaitu mampu menentukan salah benarnya sembarang prosisi matematika.
Tahun 1931, Kurt GÖdel mempublikasikan teori ketidaklengkapan dimana membuktikan prosedur/algoritma yang dikehendaki David Hilbert tersebut tidak akan pernah ada.
GÖdel membangun rumus di kalkulus predikat yang diterapkan pada bilangan bulat yang memiliki pernyataan-pernyataan definisi yang tidak dapat dibuktikan maupun dibantah di dalam sistem logika yang mungkin dibangun manusia.
Formalisasi argumen teorema ketidaklengkapan GÖdel ini berikut penjelasan dan formalisasi selanjutnya dari prosedur efektif secara intuisi merupakan salah satu pencapaian intelektual terbesar abad 20, yaitu abad dimana formalisasi berkembang semarak.
Pengembangan teori otomata, komputasi dan teori bahasa berikutnya difasilitasi perkembangan bidang psyco-linguistic. Bidang psyco-linguistic berupaya menjawab pertanyan-pertanyan berikut:
- Apakah bahasa secara umum?
- Bagaimana manusia mengembangkan bahasa?
- Bagaimana manusia memahami bahasa?
- Bagaimana manusia mengajarkan bahasa ke anak-anaknya?
- Apa gagasan-gagasan yang dapat dinyatakan dan bagaimana caranya?
- Bagaimana manusia membangun kalimat-kalimat dari gagasan-gagasan yang berada di pikirannya?
Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa komputer.
Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai sekarang belum diketahuinya bagaimana cara manusia mengartikan bahasa, sementara dengan pasti dapat mengartikan bahasa pada komputer.
Noam Chomsky mengemukakan perangkat format disebut grammar untuk memodelkan properti-properti bahasa.
Tata bahasa (grammer) bisa didefinisikan secara, formal sebagai kumpulan dari himpunan?himpunan variabel, simbol?simbol, terminal, simbol awal, yang dibatasi oleh aturan?aturan produksi. Tingkat bahasa dapat digolongkan menjadi empat yaitu :
1.Bahasa : Regular type 3
Mesin otomata : Finite State Otomata (FSA) meliputi deterministic finite automata dan non deterministic finite automata
Batasan aturan produksi : adalah sebuah simbol variabel maksimal memiliki sebuah simbol variabel yang bila terletak di posisi paling kanan.
2.Bahasa : Bebas konteks/context free /type 2
Mesin otomata : Push down automata (PDA)
Batasan aturan produksi : Berupa sebuah simbol variabel.
3.Bahasa : Context sensitive/type 1
Mesin otomata : Linier bounded automata
Batasan aturan produksi :
4.Bahasa : Unrestricted /phase /natural language/type 0
Mesin otomata : Mesin turing
Batasan aturan produksi : Tidak ada batasan
Semua aturan produksi dinyatakan dalam bentuk “” dimana
- : simbol?simbol pada ruas kiri aturan produksi
- : simbol?simbol pada ruas kanan
Simbol?simbol tersebut bisa berupa simbol terminal atau non terminal/ variabel.
Keterangan :
Simbol terminal biasanya dinyatakan dengan huruf kecil, misal 'a ', ‘b’, ‘c’.(tidak bisa diturunkan lagi).
Simbol non terminal dinyatakan dengan huruf besar, misal ‘A’, ‘B’, ‘C’.(masih bisa diturunkan).
Dengan menerapkan aturan produksi, suatu tata bahasa bisa menghasilkan string. Himpunan semua string tersebut adalah bahasa yang didefinisikan oleh tata bahasa tersebut.
Reguler
Pada bahasa reguler, batasannya bertambah dengan ruas kanan maksimal memiliki sebuah simbol variabel yang terletak di paling kanan. Artinya bisa memiliki simbol terminal saja dalam jumlah tidak dibatasi, tetapi bla terdapat simbol variabel tersebut hanya bejumlah satu (1) dan terletak di posisi paling kanan. Misal :
Bentuk normal chomsky / chomsky normal form (CNF ) merupakan salah satu bentuk normal yang sangat berguna untuk tata bahasa bebas konteks ( CFG ). Bentuk normal chomsky dapat di buat dari tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ? . dengan kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal chomsky dengan syarat :
Tidak memiliki produksi useless
Tidak memiliki produksi unit
Tidak memiliki ?
Langkah?langkah pembentukan bentuk normal chomsky secara umum:
Biarkan aturan produksi yang sudah dalam bentuk normal Chomsky.
Lakukan penggantian aturan produksi yang ruas kanannya mermiat simbol terminal dan panjang ruas kanan > 1
Lakukan penggantian aturan produksi yang ruas kanannya mernuat >2 simbol variabel
Penggantian?penggantian tersebut bisa dilakukan berkali?kali sampai akhirnya semua aturan produksi dalam bentuk normal chomsky
Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan?aturan produksi baru, dan juga memunculkan simbol?simbol variabel baru.
Free Context
Bahasa bebas konteks menjadi dasar dalam pembentukan suatu proses analisis sintaksis. Pada bahasa bebas konteks, batasannya bertambah lagi dengan ruas kiri haruslah tepat satu symbol variable.
Contoh: B ? CdeFg ; D ? BcDe
Sensiteve Context
Pada bahasa context sensitive, panjang string pada ruas kiri panjang ruas kanan ( )
Contoh : Abc ? Def ; CD ? eF
Batasan context sensitive biasanya turut digunakan dalam proses analitis semantik pada tahapan kompilasi.
Unrestricted /phase /natural language
Bahasa manusia / bahasa alami termasuk ke dalam grammer (tata bahasa) type 0 /unrestricked, di mana tidak ada batasan pada aturan produksinya.
Contoh : Abc ? De
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 abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.
· Jika w adalah sebuah string maka panjang string dinyatakan sebagai |w| dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb 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.
· Alfabet adalah hinpunan 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 Prefix(x)
· ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : ab, a, dan ε adalah semua ProperPrefix(x)
· 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.
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 simbol-simbol paling depan dari string w tersebut.
Contoh : bc, c, dan ε adalah semua ProperPostfix(x)
· Head string w adalah simbol paling depan dari string w.
Contoh : a adalah Head(x)
· Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol 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 simbol-simbol paling depan dan/atau simbol-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 simbol-simbol paling depan dan/atau simbolsimbol 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 simbol-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 simbol-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 adalah concate atau tanpa lambang apapun.
Contoh : concate(xy) = xy = abc123
· Alternation adalah pilihan satu di antara dua buah string. Operator alternation adalah alternate atau | |.
Contoh : alternate(xy) = x|y = abc atau 123
· Kleene Closure : x* = ε|x|xx|xxx|… = ε|x|x 2 |x 3 |…
Positive Closure : x + = x|xx|xxx|… = x|x 2 |x 3 |…
SIFAT OPERASI DASAR STRING
· 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
· Dua sifat aljabar concatenation :
♦ Operasi concatenation bersifat asosiatif : x(yz) = (xy)z
♦ Elemen identitas operasi concatenation adalah ε : εx = xε = 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 : ε|x + = x + |ε = x*
♦ Kesamaan ke-3 : (x|y)* = ε|x|y|xx|yy|xy|yx|… = semua string yang
merupakan concatenation dari nol atau lebih x, y, atau keduanya.

Deterministic Finite Automata (DFA) Simulator Visual Basic 6.0

 1. Buat alur DFA sebagai berikut, jangan ada perubahan. silakan d uat menggunakan sofware editing yang anda kuasai atau save gambar dari blog saya ini





2. Buat tampilan form di VB sesuai gambar di bawah ini

letakkan gambar yang tadi dibuat sebagai background


3. Buat satu modul

codenya sebagai berikut

Public Sub Fokus(ByVal KotakTesk As TextBox)
    With KotakTesk
        .SelStart = 0
        .SelLength = Len(.Text)
        .SetFocus
    End With
End Sub

3. Buka form code lalu tuliskan code berikut


Option Explicit
Dim P1, P2, P3, P4, P5 As Boolean
Dim Q1, Q2, Q3, Q4, Q5 As Boolean
Dim R1, R2, R3, R4, R5 As Boolean
Dim S1, S2, S3, S4, S5 As Boolean
Dim T1, T2, T3, T4, T5 As Boolean
Dim inputan, w, indx As Integer
Dim accept, refuses As String
Dim LenTemp, strTemp, n

Private Sub cclos_Click()
Unload Me
End Sub

Private Sub Cnew_Click()
awal
Text1.SetFocus
general.Enabled = False
w = 0
End Sub

Private Sub Cpro_Click()
general.Enabled = True
pasif
Cnew.SetFocus
End Sub

Private Sub Cpro_KeyPress(KeyAscii As Integer)
If KeyAscii = 13 Then Cnew.SetFocus
If KeyAscii = 27 Then Fokus Text5
End Sub

Private Sub Form_Load()
awal
accept = "terima"
refuses = "tolak"
strTemp = Me.Caption
n = 1
End Sub

Private Sub general_Timer()
w = w + 1
If w = 150 Then general.Enabled = False

Select Case w
    Case 0 To 25
    indx = 1
    Case 26 To 50
    inputan = Text1.Text
    indx = 2
    Case 51 To 75
    inputan = Text2.Text
    indx = 3
    Case 76 To 100
    inputan = Text3.Text
    indx = 4
    Case 101 To 125
    inputan = Text4.Text
    indx = 5
    Case 126 To 150
    inputan = Text5.Text
    indx = 6
End Select
macin
End Sub

Private Sub Text1_KeyPress(KeyAscii As Integer)
If KeyAscii = 13 Then Fokus Text2
If KeyAscii = 27 Then cclos.SetFocus
If KeyAscii = 8 Then
            KeyAscii = KeyAscii
        Else
            If KeyAscii < Asc("0") Or KeyAscii > Asc("1") Then
            KeyAscii = 0
      
        End If
    End If

End Sub

Private Sub Text2_KeyPress(KeyAscii As Integer)
If KeyAscii = 13 Then Fokus Text3
If KeyAscii = 27 Then Fokus Text1
If KeyAscii = 8 Then
            KeyAscii = KeyAscii
        Else
            If KeyAscii < Asc("0") Or KeyAscii > Asc("1") Then
            KeyAscii = 0
      
        End If
    End If

End Sub

Private Sub Text3_KeyPress(KeyAscii As Integer)
If KeyAscii = 13 Then Fokus Text4
If KeyAscii = 27 Then Fokus Text2
If KeyAscii = 8 Then
            KeyAscii = KeyAscii
        Else
            If KeyAscii < Asc("0") Or KeyAscii > Asc("1") Then
            KeyAscii = 0
      
        End If
    End If

End Sub
Private Sub Text4_KeyPress(KeyAscii As Integer)
If KeyAscii = 13 Then Fokus Text5
If KeyAscii = 27 Then Fokus Text3
If KeyAscii = 8 Then
            KeyAscii = KeyAscii
        Else
            If KeyAscii < Asc("0") Or KeyAscii > Asc("1") Then
            KeyAscii = 0
      
        End If
    End If

End Sub
Private Sub Text5_KeyPress(KeyAscii As Integer)
If KeyAscii = 13 Then
        aktif
        If Cpro.Enabled = True Then
        Cpro.SetFocus
        Else
        Cnew.SetFocus
        End If
    End If
If KeyAscii = 27 Then Fokus Text4
If KeyAscii = 8 Then
            KeyAscii = KeyAscii
        Else
            If KeyAscii < Asc("0") Or KeyAscii > Asc("1") Then
            KeyAscii = 0
      
        End If
    End If

End Sub

Private Sub Timer1_Timer()
LenTemp = Len(strTemp)
    Dim Form As String
    LenTemp = Len(strTemp)
    Me.Caption = Left(strTemp, n) + "_"
    n = n + 1
    If n > LenTemp Then
        n = 1
    End If
End Sub

Private Sub TimP_Timer()
P.FillColor = RGB(Rnd * 255, Rnd * 255, Rnd * 255)

End Sub

Private Sub TimQ_Timer()
Q.FillColor = RGB(Rnd * 255, Rnd * 255, Rnd * 255)

End Sub

Private Sub TimR_Timer()
R.FillColor = RGB(Rnd * 255, Rnd * 255, Rnd * 255)

End Sub

Private Sub TimS_Timer()
S.FillColor = RGB(Rnd * 255, Rnd * 255, Rnd * 255)

End Sub

Private Sub TimT_Timer()
T.FillColor = RGB(Rnd * 255, Rnd * 255, Rnd * 255)
X.FillColor = RGB(Rnd * 255, Rnd * 255, Rnd * 255)

End Sub

Sub awal()
TimP.Enabled = False
TimQ.Enabled = False
TimR.Enabled = False
TimS.Enabled = False
TimT.Enabled = False
general.Enabled = False
Text1.Text = ""
Text2.Text = ""
Text3.Text = ""
Text4.Text = ""
Text5.Text = ""
Label4.Caption = ""
P1 = False
P2 = False
P3 = False
P4 = False
P5 = False
Q1 = False
Q2 = False
Q3 = False
Q4 = False
Q5 = False
R1 = False
R2 = False
R3 = False
R4 = False
R5 = False
S1 = False
S2 = False
S3 = False
S4 = False
S5 = False
T1 = False
T2 = False
T3 = False
T4 = False
T5 = False
P.FillColor = vbBlack
Q.FillColor = vbBlack
R.FillColor = vbBlack
S.FillColor = vbBlack
T.FillColor = vbBlack
X.FillColor = vbWhite
pasif
End Sub

Sub macin()
Select Case indx
Case 1
    val_p
Case 2
    Select Case inputan
        Case 0
        val_q
        Q1 = True
        Case 1
        val_s
        S1 = True
    End Select
Case 3
    Select Case inputan
        Case 0
            If Q1 = True Then
                val_s
                S2 = True
            Else
            If S1 = True Then
                val_r
                R2 = True
            End If
            End If
        Case 1
        If Q1 = True Then
                val_r
                R2 = True
            Else
            If S1 = True Then
                val_t
                T2 = True
            End If
            End If
     End Select
Case 4
    Select Case inputan
    Case 0
        If S2 = True Then
                val_r
                R3 = True
            Else
        If R2 = True Then
                val_t
                T3 = True
            Else
        If T2 = True Then
                val_p
                P3 = True
            End If
        End If
    End If
    Case 1
         If S2 = True Then
                val_t
                T3 = True
            Else
        If R2 = True Then
                val_q
                Q3 = True
            Else
        If T2 = True Then
                val_r
                R3 = True
            End If
        End If
    End If
    End Select
Case 5
    Select Case inputan
        Case 0
            If R3 = True Then
                val_t
                T4 = True
            Else
            If T3 = True Then
                val_p
                P4 = True
            Else
            If P3 = True Then
                val_q
                Q4 = True
            Else
            If Q3 = True Then
                val_s
                S4 = True
            End If
            End If
        End If
        End If
    Case 1
        If R3 = True Then
                val_q
                Q4 = True
            Else
            If T3 = True Then
                val_r
                R4 = True
            Else
            If P3 = True Then
                val_s
                S4 = True
            Else
            If Q3 = True Then
                val_r
                R4 = True
            End If
            End If
        End If
        End If
    End Select
Case 6
    Select Case inputan
        Case 0
            If T4 = True Then
                val_p
                Label4.Caption = refuses
            Else
            If S4 = True Then
                val_r
                Label4.Caption = refuses
            Else
            If R4 = True Then
                val_t
                Label4.Caption = accept
            Else
            If Q4 = True Then
                val_s
                Label4.Caption = refuses
            Else
            If P4 = True Then
                val_q
                Label4.Caption = refuses
                End If
            End If
        End If
        End If
        End If
    Case 1
            If T4 = True Then
                val_r
                Label4.Caption = refuses
            Else
            If S4 = True Then
                val_t
                Label4.Caption = accept
            Else
            If R4 = True Then
                val_q
                Label4.Caption = refuses
            Else
            If Q4 = True Then
                val_r
                Label4.Caption = refuses
            Else
            If P4 = True Then
                val_s
                Label4.Caption = refuses
                End If
            End If
        End If
        End If
        End If
    End Select
End Select
End Sub

Sub val_p()
TimP.Enabled = True
TimQ.Enabled = False
Q.FillColor = vbBlack
TimR.Enabled = False
R.FillColor = vbBlack
TimS.Enabled = False
S.FillColor = vbBlack
TimT.Enabled = False
T.FillColor = vbBlack
X.FillColor = vbWhite

End Sub

Sub val_q()
TimP.Enabled = False
P.FillColor = vbBlack
TimQ.Enabled = True
TimR.Enabled = False
R.FillColor = vbBlack
TimS.Enabled = False
S.FillColor = vbBlack
TimT.Enabled = False
T.FillColor = vbBlack
X.FillColor = vbWhite

End Sub
Sub val_r()
TimP.Enabled = False
P.FillColor = vbBlack
TimQ.Enabled = False
Q.FillColor = vbBlack
TimR.Enabled = True
TimS.Enabled = False
S.FillColor = vbBlack
TimT.Enabled = False
T.FillColor = vbBlack
X.FillColor = vbWhite


End Sub
Sub val_s()
TimP.Enabled = False
P.FillColor = vbBlack
TimQ.Enabled = False
Q.FillColor = vbBlack
TimR.Enabled = False
R.FillColor = vbBlack
TimS.Enabled = True
TimT.Enabled = False
T.FillColor = vbBlack
X.FillColor = vbWhite


End Sub
Sub val_t()
TimP.Enabled = False
P.FillColor = vbBlack
TimQ.Enabled = False
Q.FillColor = vbBlack
TimR.Enabled = False
R.FillColor = vbBlack
TimS.Enabled = False
S.FillColor = vbBlack
TimT.Enabled = True


End Sub



Sub pasif()
Cpro.Enabled = True
End Sub

Sub aktif()
If Not Text1.Text = "" And Not Text2.Text = "" And Not Text3.Text = "" And Not Text4.Text = "" And Not Text5.Text = "" Then
Cpro.Enabled = True
End If
End Sub


posting dari  blog nya:

Penerapan Konsep bahasa dan Automata dalam keilmuan

             Sejarah Teori bahasa dan automata

 
           
Sebelum kita mengkaji penerapan ataupun imlplementasi dari konsep bahasa dan Automata ada baiknya kita mengetahui perkembangan ataupun sejarah dari automata dan tiori bahasa
           
Otomata bermula sebelum komputer ada pada teori di bidang sistem logika matematika atau formal, ilmuwan David Hilbert telah mencoba menciptakan algoritma umum untuk pembuktian (seluruh) persoalan matematika secara otomatis yaitu mampu menentukan salah benarnya sembarang prosisi matematika.
           
Tahun 1931, KurtGdel mempublikasikan teori ketidaklengkapan dimana membuktikan prosedur/algoritma yang dikehendaki David Hilbert tersebut tidak akan pernah ada. KurtGdel membangun rumus di kalkulus predikat yang diterapkan pada bilangan bulat yang memiliki pernyataan-pernyataan definisi yang tidak dapat dibuktikan maupun dibantah di dalam sistem logika yang mungkin dibangun manusia.
           
Formalisasi argumen teorema ketidaklengkapan KurtGdel ini berikut penjelasan dan formalisasi selanjutnya dari prosedur efektif secara intuisi merupakan salah satu pencapaian intelektual terbesar abad 20, yaitu abad dimana formalisasi berkembang semarak.
            Pengembangan teori otomata, komputasi dan teori bahasa berikutnya difasilitasi perkembangan bidang psyco-linguistic. Bidang psyco-linguistic berupaya menjawab pertanyan-pertanyan berikut:
 
- Apakah bahasa secara umum?
- Bagaimana manusia mengembangkan bahasa?
- Bagaimana manusia memahami bahasa?
- Bagaimana manusia mengajarkan bahasa ke anak-anaknya?
- Apa gagasan-gagasan yang dapat dinyatakan dan bagaimana caranya?
- Bagaimana manusia membangun kalimat-kalimat dari gagasan-gagasan yang berada di pikirannya?
           
Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa computer.
           
Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai sekarang belum diketahuinya bagaimana cara manusia mengartikan bahasa, sementara dengan pasti dapat mengartikan bahasa pada komputer.Noam Chomsky mengemukakan perangkat format disebut grammar untuk memodelkan properti-properti bahasa.Grammar berisi sejumlah aturan serta menspesifikasikan bahasa tertentu.Bahasa berisi semua string yang dapat dihasilkan menggunakan aturan-aturan grammar.
           
Meski pembahasan Chomsky terutama ditujukan untuk bahasa alami, grammar mempunyai nilai/manfaat sangat besar di ilmu informatika/komputer karena pencapaian ini digunakan untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal lainnya.
           
Grammar diterapkan pada perancangan kompilator dan bidang-bidang di ilmu komputer.McCulloch dan Pittsmengemukakan Mesin Abstrak sederhana yaitu finite automata untuk memodelkan neuron nets.Finite automata juga digunakan untuk merancang switching circuit.
 
Studi mengenai teori otomata terkait bidang-bidang lain di ilmu komputer.Kemudian ekivalensi antara finite automata dan ekspresi reguler (reguler expression) dikemukakan Stephen Kleene. Sejak saat itu teori bahasa dikaitkan secara erat dengan teori bahasa formal. ubungan teori otomata dan teori pengkodean (coding theory) juga banyak diteliti.
           
Turing machine seperti komputer modern saat ini dapat mengolah (simbol-simbol di tape) dan mengahasilkan keluaran (simbol-simbol yang berada di tapenya setelah berakhirnya sebarisan pergerakkan) merupakan karya teoritis dari Alan Turing.
  • Penerapan Bahasa dan Automata Dalam konsep Keilmuan
            Teori automata yang selama ini lebih banyak diterapkan dalam bidang tata bahasa formal khususnya dalam pengembangan sebuah compiler, juga dapat digunakan untuk melakukan pemodelan dan pendekatan pemecahan masalah masalah yang berkaitan dengan aplikasi-aplikasi di dalam bidang kecerdasan Buatan. Bahkan pada beberapa masalah spesifik yang berkaitan dengan keputusan dan model mesin hanya tepat jika solusinya didasarkan pada solusi automata.Kelebihan penggunaan teori automata dibanding pohon keputusan dalam memodelkan ruang keadaan adalah lebih sederhana jika terdapat beberapa keadaan yang berulang. Penerapan teoritis automata untuk pengembangan suatu sistem adalah dengan menggunakan teori automata sebagai sebuah paradigma yang menggabungkan spesifikasi sistem, verifikasi dan sintesis.
 
A.Kecerdasan buatan
 
            Kecerdasan Buatan adalah bidang ilmu yang mendasarkan bagaimana sebuah komputer bisa bertindak seperti dan sebaik manusia. Dewasa ini, Penggunaan kecerdasan buatan dibutuhkan diberbagai disiplin ilmu. Irisan antara psikologi dan kecerdasan Buatan melahirkan area cognition and psycolinguistic. Irisan antara teknik elektro dengan kecerdasan buatan melahirkan ilmu : pengolahan citra, teori kendali, pengenalan pola dan robotika. Irisan ilmu manajemen dan kecerdasan buatan menghasilkan sistem pendukung keputusan. Adanya irisan penggunaan kecerdasan buatan diberbagai disiplin ilmu menyebabkab cukup rumitnya untuk mengklasifikasikan lingkup bidang ilmu kecerdasan buatan, sehingga pengklasifikasian lingkup kecerdasan buatan didasarkan pada output yang diberikan yaitu pada aplikasi komersial.
Lingkup aplikasi kecerdasan buatan meliputi :
 
1. sistem pakar
 
2. Pengolahan bahasa alami
 
3. Pengenalan ucapan
 
4. Robotika dan sistem sensor
 
5. Computer vision
 
6. Problem solving and planning
 
7. Permainan

Pengembangan Konverter Fonem ke Suara untuk Aplikasi Alat Bantu Wicara menggunakan Extended Finite State Automata


Konverter teks ke fonem berfungsi untuk memecah sebuah kalimat atau kata menjadi bentuk pecahan terkecil dari sebuah pengucapan atau sering dinamakan bentuk fonem (suku kata). Output berupa fonem yang dihasilkan konverter ini akan menjadi input dari sistem konverter selanjutnya konverter fonem ke wicara. Makalah ini merupakan pengembangan lebih lanjut Konverter teks ke fonem menggunakan mikrokontroler (ATMEGA 16L) sebagai penyimpan dan pemroses program, masukan berupa teks diketikkan melalui keypad 3x4. Algoritma program yang dipakai untuk memecah kata menjadi fonem berdasarkan referensi dari teknik finite state automata [4] yang dikembangkan lebih lanjut sehingga mampu mendeteksi difong. Pola fonem yang berhasil dikenali adalah pola fonem regular atau dasar dari pola suku kata dalam bahasa Indonesia. Sehingga untuk kata-kata asing/serapan yang telah dimasukkan tetap akan dipecah berdasar pola fonem ejaan bahasa Indonesia. Konverter teks ke fonem ini juga telah dapat mengenali bentuk karakter berupa angka (normalisasi angka). Konverter teks ke fonem ini memiliki akurasi 100% untuk pola fonem regular bahasa Indonesia serta sifat portable, karena bentuknya yang tergolong kecil dan mudah untuk dibawa kemana mana. Kelemahan dari konverter ini adalah belum tersedianya pengenalan karakter berupa tanda baca

Otomata

Teori Bahasa dan Otomata

Bahasa adalah struktur yang dikendalikan sekumpulan aturan tertentu, semacam mesin untuk memproduksi makna. Akan tetapi seperti setiap mesin hanya terdapat kemungkinan terbatas bagi setiap orang dalam menggunakannya.

Dalam bahasa disediakan pembendaharaan kata atau tanda (vocabulary), serta perangkat aturan bahasa (grammar, sintaks) yang harus dipatuhi jika hendak menghasilkan sebuah ekspresi yang bermakna.

Proses Kemampuan Pemahaman Bahasa

Hipotesis Noam Chomsky menggugat postulat John Locke (tokoh empirisme) yang menyatakan segala pengetahuan yang dimiliki manusia berasal dari rangsangan-rangsangan luar (pengalaman) yang ditangkap oleh indera-indera manusia, sehingga meniadakan pengetahuan apriori (pengetahuan yang langsung tertanam di manusia)

Noam Chomsky menyandarkan pada pemahaman bahasa sebagai sesuatu yang bersifat khas dan bawaan (tertanam) pada manusia sejak lahir.

Secara khusus Chomsky dipengaruhi Descartes tentang bahasa dan pikiran yang terikat begitu erat sehingga pengetahuan tentang bahasa bisa membuka pengetahuan tentang pikiran manusia.

Secara mendasar bahasa adalah bagian psikologi manusia yang dipahami sebagai teori tentang kemampuan pikiran manusia berupa ungkapan dari subjek psikologi.

Chomsky dan para ahli bahasa telah mengamati anak kecil mampu menjadi lancar berbahasa lebih cepat dan mudah dibanding "algoritma belajar berbahasa".

Sehingga para ahli bahasa membuat hipotesis otak berisi/memuat suatu "mesin bahasa umum". Kemudian selama masa awal pertumbuhan anak, terjadi pertemuan dengan bahasa sehari-hari yang mengubah mesin bahasa umum menjadi mesin bahasa partikular (tertentu) ke bahasa spesifik.


Teori Bahasa

Teori Bahasa adalah konsep-konsep pada "string alpabet V" dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (bahasa).

- Alpabet

Adalah himpunan simbol (karakter) tak kosong yang berhingga. Alpabet digunakan untuk membentuk kata-kata (string-string) di bahasa. Bahasa dimulai dengan alpabet. Pada beberapa buku, alpabet dilambangkan dengan Σ

Istilah huruf, karakter dan simbol adalah sinonim menunjukkan elemen alpabet. Jika simbol berbaris bersebelahan, maka diperoleh "string simbol". Istilah kalimat, kata dan string adalah sinonim

Contoh :
{a,b} -> Himpunan yang terdiri dari simbol "a" dan "b".


- Penyambungan (Concatenation - o)

Penyambungan dilakukan pada 2 karakter atau lebih membentuk 1 barisan karakter (string simbol).

Contoh :
'a' o 'b' = 'ab'
'ab' o 'baab' = 'abbaab'


- String pada alpabet V
Karakter atau barisan karakter pada alpabet V dibentuk dari penyambungan karakter pada alpabet V.

String pada alpabet V adalah deretan (sekeun) simbol dari V dimana perulangan simbol diijinkan.

Contoh :
V = {a,b,c,d}
String pada alpabet V antara lain -> 'a','abcd','bbba'

Pemangkatan
Penyambungan dapat dianggap sebagai perkalian karena biasanya penulisannya adalah bila x dan y string, maka x o y adalah xy. sehingga pemangkatan dapat digunakan

VoV = VV = V2 ----> Panjang string = 2
VoVoV = V2oV=V3 -> Panjang string = 3
VoVoVoV = N4 ----> Panjang string = 4
VoVoVo...oV=Vn ---> Panjang string = n


Vk = VoVoVo...oV
adalah himpunan string dengan panjang k, masing-masing simbol adalah alpabet V

V* = {ε} U V+ (Kleene closure)
adalah string pada V, termasuk string kosong dimana ε string kosong (string tanpa simbol)
ε mempunyai sifat identitas, yaitu:
ε o x = x
x o ε = x

V+ = V1 U V2 U V3 U ... (Positive closure)
adalah himpunan string pada V, tidak ada string kosong didalamnya.

V0 = {ε}
adalah himpunan yang isinya hanya string kosong, dimana String kosong ε tidak sama dengan himpunan kosong �


Maka 'bbba' dapat ditulis 'b3a'


Panjang String
Panjang string dilambangkan |w| dimana panjang string adalah jumlah simbol di dalam string bukan pada alpabet dan pengulangan kemunculan simbol dihitung.

Contoh:
|ε| = 0
|a| = 1
|aa| = 2
|aaa| = 3
|aaab| = 4



Otomata

Otomata adalah mesin abstrak yang menggunakan model matematika, tetapi matematika yang digunakan benar-benar berbeda dibanding matematika klasik dan kalkulus. Model yang digunakan adalah model mesin state (state machine model) atau model trnasisi state (state transition model).

Terdapat 3 model komputasi pada teori otomata.
- Finite automata
- Pushdown automata
- Turing Mavhine


Memori Otomata

Otomata dibedakan berdasarkan jenis memori sementara yang dimilikinya, yaitu:

- Finite automata (FA)
Tidak memiliki memori sementara. Finite automata adalah kelas mesin dengan kemampuan-kemampuan paling terbatas.

- Pushdown automata (PDA)
Memiliki memori sementara dengan mekanisme LIFO (Last In, First Out). Mesin ini lebih ampuh karena bantuan keberadaan stack yang dipandang sebagai unit memori

- Turing Machine (TM)
Memiliki memori dengan mekanisme pengaksesan acak (Random akses memori). Turing Machine merupakan model matematika untuk komputer saat ini.


Sejarah Otomata dan Teori Bahasa

Otomata bermula sebelum komputer ada pada teori di bidang sistem logika matematika atau formal, ilmuwan David Hilbert telah mencoba menciptakan algoritma umum untuk pembuktian (seluruh) persoalan matematika secara otomatis yaitu mampu menentukan salah benarnya sembarang prosisi matematika.

Tahun 1931, Kurt G�del mempublikasikan teori ketidaklengkapan dimana membuktikan prosedur/algoritma yang dikehendaki David Hilbert tersebut tidak akan pernah ada.

G�del membangun rumus di kalkulus predikat yang diterapkan pada bilangan bulat yang memiliki pernyataan-pernyataan definisi yang tidak dapat dibuktikan maupun dibantah di dalam sistem logika yang mungkin dibangun manusia.

Formalisasi argumen teorema ketidaklengkapan G�del ini berikut penjelasan dan formalisasi selanjutnya dari prosedur efektif secara intuisi merupakan salah satu pencapaian intelektual terbesar abad 20, yaitu abad dimana formalisasi berkembang semarak.

Pengembangan teori otomata, komputasi dan teori bahasa berikutnya difasilitasi perkembangan bidang psyco-linguistic. Bidang psyco-linguistic berupaya menjawab pertanyan-pertanyan berikut:
- Apakah bahasa secara umum?
- Bagaimana manusia mengembangkan bahasa?
- Bagaimana manusia memahami bahasa?
- Bagaimana manusia mengajarkan bahasa ke anak-anaknya?
- Apa gagasan-gagasan yang dapat dinyatakan dan bagaimana caranya?
- Bagaimana manusia membangun kalimat-kalimat dari gagasan-gagasan yang berada di pikirannya?

Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa komputer.

Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai sekarang belum diketahuinya bagaimana cara manusia mengartikan bahasa, sementara dengan pasti dapat mengartikan bahasa pada komputer.

Noam Chomsky mengemukakan perangkat format disebut grammar untuk memodelkan properti-properti bahasa.

Grammar berisi sejumlah aturan serta menspesifikasikan bahasa tertentu.

Bahasa berisi semua string yang dapat dihasilkan menggunakan aturan-aturan grammar.

Meski pembahasan Chomsky terutama ditujukan untuk bahasa alami, grammar mempunyai nilai/manfaat sangat besar di ilmu informatika/komputer karena pencapaian ini digunakan untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal lainnya.

Grammar diterapkan pada perancangan kompilator dan bidang-bidang di ilmu komputer.

McCulloch dan Pitts mengemukakan Mesin Abstrak sederhana yaitu finite automata untuk memodelkan neuron nets.

Finite automata juga digunakan untuk merancang switching circuit. Studi mengenai teori otomata terkait bidang-bidang lain di ilmu komputer.

Kemudian ekivalensi antara finite automata dan ekspresi reguler (reguler expression) dikemukakan Stephen Kleene. Sejak saat itu teori bahasa dikaitkan secara erat dengan teori bahasa formal. ubungan teori otomata dan teori pengkodean (coding theory) juga banyak diteliti.

Turing machine seperti komputer modern saat ini dapat mengolah (simbol-simbol di tape) dan mengahasilkan keluaran (simbol-simbol yang berada di tapenya setelah berakhirnya sebarisan pergerakkan) merupakan karya teoritis dari Alan Turing.

Karena banyak yang berperan pada pengembangannya, bidang teori ini diberi aneka ragam nama yaitu:
- teori otomata (theory of automata)
- teori bahasa formal (theory of formal language)
- teori mesin turing (theory of Turing machine).

posting ini di ambil dari situs global komputer

Ekspresi Reguler

Asal Gagasan Ekspresi Reguler


Permulaaan gagasan ekspresi reguler dikemukakan pada tahun 1940 oleh Warren McCulloch dan Walter Pitts.

Bidang keahlian mereka adalah neuro-physiologist. Mereka mengembangkan model sederhana mengenai sistem syaraf pada level neuron.

Ekspresi reguler menjadi nyata secara formal ketika matematikawan Stephen Kleene mendeskripsikan model-model yang ditemukan McCulloch dan Pitts ini secara formal dalam 1 aljabar yang disebut himpunan reguler.

Stephe Kleene mengemukakan notasi sederhana untuk mengekspresikan himpunan reguler ini disebut ekspresi reguler.

Pada tahun 1950 dan 1960-an, ekspresi reguler memperoleh perhatian para matematikawan. Pada tahun 1968, Ken Thompson menggunakan ekspresi reguler untuk persoalan komputasi, ditulis dalam makalah berjudul "Reguler Expression Search Algorithm" yang mendeskripsikan kompilator ekspresi reguler sehingga menghasilkan kode objek untuk komputer 8094.


Himpunan Reguler

Adalah himpunan (alpabet) berhingga dengan ketentuan (apabila VT sebagai himpunannya):

1. � (himpunan kosong) merupakan bagian dari himpunan reguler pada VT
2. {ε} merupakan bagian dari himpunan reguler pada VT
3. {a} merupakan bagian dari himpunan reguler pada VT
4. Jika P dan Q merupakan bagian himpunan reguler pada VT, maka begitu juga
-- a. P U Q
-- b. PQ
-- c. P*
5. Tidak ada yang selain itu yang merupakan himpunan reguler


Ekpresi Reguler
Ekspresi Reguler adalah rumusan yang berbentuk bagus (well-formed formula) pada :
- Operasi gabungan (union, dilambangkan dengan + )
- Penyambungan (concatenation, dilambangkan dengan simbol yang bersebelahan)
- Kleene closure (dilambangkan dengan * )

Pada pendefinisiannya (apabila VT sebagai himpunannya):
1. � = ekspresi reguler yang menunjukkan himpunan reguler �
2. ε = ekspresi reguler yang menunjukkan himpunan reguler ε
3. a pada VT = ekspresi reguler yang menunjukkan himpunan reguler {a}
4. Jika p dan q adalah ekspresi reguler yang menunjukkan himpunan reguler P dan Q, maka
-- a. (p+q) adalah ekspresi reguler yang menunjukkan P U Q
-- b. (pq) adalah ekspresi reguler yang menunjukkan PQ
-- c. (p)* adalah ekspresi reguler yang menunjukkan P*
5. Tidak ada yang selain itu yang merupakan ekspresi reguler


Prioritas operasi

Untuk penyederhanaan penulisan, perlu diperhatikan hal-hal seperti Tanda kurung dihilangkan bila tidak muncul ambiguitas (memiliki lebih dari 1 arti yang berbeda)
dimana urutan prioritasnya adalah dimulai dari:
- Kleene closure
- penyambungan
- gabungan, +,

contoh:
- 0+10* => 0+1(0*)
=> 0+(1(0*))
=> (0+(1(0*)))
maka 0+10* singkatan dari (0+(1(0*)))

- (001)* adalah singkatan dari (((0)1)*)

- 1*10+11* adalah singkatan dari ((((1)*1)0)+(1(1)*))


Konvensi

Ekpresi Reguler p+ menunjukkan string simbol pp*

yaitu:
p+ = p
pp* = pε = p, dimana ε merupakan elemen dari p*

contoh:

- Ekspresi reguler
menunjukkan elemen himpunan � saja (konstan)
untuk umumnya menjadi himpunan{�}

- Ekspresi reguler 001
menunjukkan elemen himpunan 001 saja (konstan)
untuk umumnya menjadi himpunan{001} yaitu {0}{0}{1}

- Ekspresi reguler 0+10
menunjukkan elemen himpunan 0 bisa juga 10
untuk umumnya menjadi himpunan{0,10} yaitu {0} U {10}

- Ekspresi reguler 0*
menunjukkan elemen himpunan "string simbol (gabungan simbol)" dapat memiliki kemungkinan :
ε
0
00
000
dan kemungkinan-kemungkinan lainnya
untuk umumnya menjadi himpunan {0}*

- Ekspresi reguler (0+1)*
menunjukkan elemen himpunan "string simbol" dengan memiliki kemungkinan :
ε
0
1
01
10
dan kemungkinan-kemungkinan lainnya
untuk umumnya menjadi himpunan {0,1}*

- Ekspresi reguler (0+1)*011
menunjukkan elemen himpunan "string simbol" dengan memiliki kemungkinan :
ε011(=011)
0011
1011
01011
10011
dan kemungkinan-kemungkinan lainnya
Dimana setiap string simbol selalu diakhir "011" yang konstan pada (0+1)*011
untuk umumnya menjadi himpunan {0,1}*{011}

- Ekspresi reguler (a+b)(a+b+0+1)*
menunjukkan elemen himpunan "string simbol" dengan memiliki kemungkinan :
aε(=a) atau bε(=b)
aa bisa juga ba
ab bisa juga bb
a0 bisa juga b0
a1 bisa juga b1
aaa bisa juga baa
aab bisa juga bab
aa0 bisa juga ba0
aa1 bisa juga ba1
aba bisa juga bba
abab bisa juga bbab
dan kemungkinan-kemungkinan lainnya
Dimana setiap string simbol selalu diawali "a" bisa juga "b" yang konstan pada (a+b)(a+b+0+1)*
untuk umumnya menjadi himpunan {a,b}{a,b,0,1}*

- Ekspresi reguler 1*10
menunjukkan elemen himpunan "string simbol" dengan memiliki kemungkinan :
ε10(=10)
110
1110
11110
dan kemungkinan-kemungkinan lainnya
Dimana setiap string simbol selalu diakhir "10" yang konstan pada 1*10
untuk umumnya menjadi himpunan {1}*{10}

- Ekspresi reguler (00+11)*((01+10)(00+11)*(01+11)*)*
dengan pengandaian menjadi a*(bc*d*)*
juga dapat menjadi a*e* dimana e = bc*d*
menunjukkan elemen himpunan "string simbol" dengan memiliki kemungkinan :
ε => a dan e adalah ε
01 bisa juga 10 => a,c,d adalah ε
0100 bisa juga 1000 => a,d adalah ε
0111 bisa juga 1011 => a,d adalah ε
010000 bisa juga 100000 => a,d adalah ε
010011 bisa juga 100011 => a,d adalah ε
010001 bisa juga 100001 => a adalah ε
010011 bisa juga 100011 => a adalah ε
011101 bisa juga 101101 => a adalah ε
011111 bisa juga 101111 => a adalah ε
0100111101 bisa juga 1000111101 => a adalah ε
00 bisa juga 11 => e adalah ε
0011 bisa juga 1111 => e adalah ε
0000 bisa juga 1100 => e adalah ε
0001 bisa juga 1101 => c dan d adalah ε
000001 bisa juga 110001 => c dan d adalah ε
dan kemungkinan-kemungkinan lainnya
untuk umumnya menjadi himpunan
{00,11}*({01,10}{00,11}*{01,11}*)*