TEORI BAHASA & AUTOMATA

Sejarah Otomata

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.  Otomata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. 

Teori bahasa dan otomata merupakan bagian dari teori komputasi pada ilmu komputer. Beberapa teori komputasi datang dari bahasa dan rekayasa sistem, terutama yang berbasiskan matematika. Dalam hal ini penekanannya adalah pada pemecahan masalah.

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 ;[1]
• 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

Definisi Formal

Otomata adalah sebuah 5-tupel :

•  adalah himpunan berhingga dari state,
•  adalah himpunan simbol-simbol,
•  adalah fungsi transisi
•  adalah simbol awal
•  adalah state akhir

Jenis-jenis Otomata

Otomata Berhingga Deterministik

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

Contoh

Konfigurasi DFA disamping secara formal dinyatakan sebagai berikut Q = {q0, q1, q2, q3 } Σ = {0,1} S = q0 F = { q0}
Fungsi transisi, biasanya fungsi-fungsi transisi ini kita sajikan dalam sebuah tabel transisi. Tabel transisi tersebut menunjukkan state state berikutnya untuk kombinasi state state dan input. Tabel transisi dari fungsi transisi adalah

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

Fungsi transisi dalam NFA memetakan pasangan  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.

Contoh NFA

• String diterima NFA bila terdapat suatu urutan transisi berdasarkan input, dari state awal ke state akhir.
• harus mencoba semua kemungkinan.