Teori otomata

Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal. ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

Konsep Dasar

• Anggota alfabet dinamakan simbol terminal.

• Kalimat adalah deretan hingga simbol-simbol terminal.

• Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.

• Simbol-simbol berikut adalah simbol terminal :

huruf kecil, misalnya : a, b, c
simbol operator, misalnya : +, , dan *
simbol tanda baca, misalnya : (, ), dan ;
simbol tanda baca, misalnya : (, ), dan ;
string yang tercetak tebal, misalnya : if, then, dan else.

• Simbol-simbol berikut adalah simbol non terminal /Variabel :

huruf besar, misalnya : A, B, C
huruf S sebagai simbol awal
string yang tercetak miring, misalnya : expr

• Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : α,β, dan ε

• Sebuah produksi dilambangkan sebagai α --> β, artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol α dengan simbol β.

• Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : α ==> β.

• Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.

• Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah merupakan sentensial, sebaliknya belum tentu.. Grammar :

Grammar G didefinisikan sebagai pasangan 4 tuple : V_t , V_n , S, dan P, dan dituliskan sebagai G(V_t , V_n , S, P), dimana :

V_t : himpunan simbol-simbol terminal (alfabet) = kamus V_n : himpunan simbol-simbol non terminal S C V : simbol awal (atau simbol start) P : himpunan produksi

Contoh :

1. G1 : VT = {I, want, need, You}, V = {S,A,B,C}, P = {S --> ABC, A--> I, B--> want | need, C--> You}

S --> ABC

  --> IwantYou

L(G1)={IwantYou,IneedYou}

2. . G2 : VT = {a}, V = {S}, P = {S  aS | a}

S --> aS

 --> aaS
 --> aaa                    L(G2) ={an --> n ≥ 1}

            L(G2)={a, aa, aaa, aaaa,…}

Otomata Berhingga

Definisi Formal

Otomata adalah sebuah 5-tupel $\langle Q,\Sigma ,\delta ,q_{0},F\rangle$ :

$Q$ adalah himpunan berhingga dari state,
$\Sigma$ adalah himpunan simbol-simbol,
$\delta$ adalah fungsi transisi
$q_{0}\in Q$ adalah simbol awal
$F\subset Q$ adalah state akhir

Jenis-jenis Otomata Berhingga

Otomata Berhingga Deterministik

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

\delta :Q\times \Sigma \rightarrow Q

Otomata Berhingga Non-Deterministik

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

\delta :Q\times \Sigma \rightarrow {\mathcal {P}}(Q)

Fungsi transisi dalam NFA memetakan pasangan $Q$ dan $\Sigma$ 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.

Otomata Pushdown

Otomata Pushdown adalah salah satu varian otomata dengan 7-tupel $\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},Z_{0},F\rangle$ , di mana:

$Q$ adalah himpunan berhingga dari state,
$\Sigma$ adalah himpunan simbol-simbol,
$q_{0}\in Q$ adalah simbol awal
$F\subset Q$ adalah state akhir

Ditambah dengan dua unsur, untuk menangani stack:

$\Gamma$ adalah himpunan berhingga simbol-simbol stack,
$Z_{0}\in \Gamma$ adalah simbol awal stack,

Dengan fungsi transisinya adalah

\delta :Q\times (\Sigma \cup \{\epsilon \})\times \Gamma )\rightarrow Q\times \Gamma ^{*}

adalah fungsi transisi

Otomata Terbatas Linear

Mesin Turing

Kecerdasan artifisial (demi kemudahan, mulai sekarang sebut saja AI) pada mulanya adalah:

   studi tentang sifat-sifat formal (mekanis atau komputasional) dari masalah-masalah dan metode-metode pemecahan masalah, dengan bantuan komputer yang dilengkapi kemampuan memecahkan masalah yang bisa dibandingkan dengan kemampuan manusia.

Kita akan kembali meninjau AI di bagian-bagian selanjutnya, dan untuk saat ini, kita lihat dulu, ada apa dibalik 'sifat-sifat formal' di atas, yang mekanis atau yang komputasional. Sementara, mekanis maupun komputasional kita anggap setara dulu, meski nanti mempunyai perbedaan tipis tapi kritis ketika bertemu masalah pembumian simbol dan argumen ruang Cina.

Komputasi sendiri pertama kali dianggap sebagai model kognisi sejak ditemukannya arsitektur standar komputer yang dipakai sampai sekarang. Tahun 1930-an, dengan kerja awal Alan Turing, seorang logikawan, ide tentang pemakaian komputer digital untuk pemecahan berbagai masalah mulai ditawarkan.

Turing memperkenalkan Mesin Turing, sebuah mesin imajiner yang mempunyai pita dengan panjang tak terbatas, dan pita ini mempunyai sel-sel yang bisa mewakili string atau urutan karakter tertentu; analog dengan hardisk sebuah komputer sekarang. Selain itu, MT juga punya head yang bisa membaca, lalu menulis atau membiarkan string yang ada di pita; berfungsi mirip kontroler hardisk. Setiap pembacaan, penulisan, atau pembiaran string oleh head diwakili oleh suatu keadaan (state), disertai arah head harus bergerak menuju sel selanjutnya, kiri atau kanan.

Terakhir, apa yang harus ditulis ke pita, arah gerak head, dan perpindahan keadaan ditentukan dalam sebuah tabel, misalnya, baris pertama tabel berisi {q1,q2,0,#,R}, disusul baris kedua berisi {q2,qh,#,#,L}. Artinya, dari keadaan q1, jika di pita tertulis 0, maka hapuslah isinya (tulislah '#') dan geraklah ke kanan R, dan masuki keadaan q2. Setelah bergerak ke kanan, jika ketemu tanda '#' di sel selanjutnya, maka biarkan tanda itu, dan geraklah ke kiri L. Demikian cara kerja sebuah mesin sederhana yang bisa menghapus tanda '0' di pita, dan akhirnya MT masuk ke qh, keadaan halt. Jika ada input yang tidak cocok dengan isi tabel, maka MT tidak akan mencapai qh, dan mesinnya nge-hang.

Cukup dengan arsitektur sederhana ini, Turing—dan Alonzo Church secara terpisah—menawarkan tesis Church-Turing: MT mempunyai kekuatan komputasi yang sama dengan mesin deterministik manapun. Oleh John von Neumann, dibentuk mesin yang bisa memindahkan sebagian tabel di pita (ingat virtual memory atau swap?), sehingga membuat sebuah tabel berarti menulis sebuah program seperti yang kita kenal sekarang.

Percaya atau tidak, performa PC atau Mac yang bisa menyelesaikan berbagai masalah saat ini, bila kita lihat 'bahasa tingkat bawah'-nya, tetap saja berisi perintah-perintah membaca dan menulis ulang isi pita. Bedanya misalnya, pitanya berwujud semikonduktor yang bisa menyimpan banyak data (atau string di sel) yang bisa diakses dengan cepat (membaca - menulis-ulang - ke kiri - ke kanan), dan meskipun digital, nilai bit 0 atau 1 di sel dikelompokkan oleh bahasa mesin menjadi byte dan setiap byte mewakili satu simbol yang menghuni secuil sektor di sebuah trek hardisk.

Untuk banyak kasus, misalnya linguistik (mis.: mengecek gramatikalitas sebuah urutan string sehingga bisa dianggap sebagai kalimat atau tidak), kadang MT terlalu mewah. Kita cukup menemukan bentuk-bentuk mesin (atau otomata) yang lebih sederhana, misalnya FSA, finite-state automata yang tidak punya pita yang bisa ditulisi sama sekali, atau PDA, push-down automata yang punya pita terbaca dan tertulisi (disebut stack) secara terpisah.

Nanti, fakta bahwa kognisi bisa dianggap sebagai kemampuan berbahasa dan bahasa bisa direpresentasikan secara komputasional akan dijelaskan lebih lanjut. Demikian pula fakta bahwa kognisi juga bisa dianggap sebagai kemampuan masalah yang digambarkan dalam manipulasi simbol-simbol. AI, di satu dan lain hal, adalah manipulasi simbol-simbol dengan bantuan logika simbolik.

Untuk saat ini, ide tentang keumuman dari kemampuan MT sudah tergambarkan, misalnya, MT tidak hanya bisa mengenali, tapi juga, karena perpindahan keadaannya tak dibatasi (sesuka kita menulis programnya), bisa mengeluarkan input yang tidak terbatas. Belum ada yang membantah tesis Church-Turing atau belum ada yang membuat komputer dengan arsitektur lain secanggih punya MT tetapi tidak ekivalen atau tidak bisa dicari padanan MT-nya.

Masalahnya, seberapa umumkah keumuman MT? []

Hubungan dengan Tata Bahasa

Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu.

Referensi

John E. Hopcroft, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation

Artikel bertopik matematika ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.