KONSEP DALAM TEORI OTOMATA

Teori Bahasa 

• Teori bahasa membicarakan tentang bahasa formal (formal language), terutama untuk perancangan kompilator (compiler) dan pemroses naskah (text processor). 
• Bahasa formal adalah kumpulan kalimat. 
• Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar).

Otomata (Automata) 

• Adalah mesin abstrak yang dapat mengenali  (recognize), menerima( accept) atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

Otomata

• Arti menurut American Heritage Dictionary:
• a robot
• one that behaves in an automatic or mechanical fashion
• Arti dalam dunia matematika
• Berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input, dan mengeluarkan output, dalam bentuk diskrit.

Contoh :

• Mesin Jaja / vending machine
• Kunci kombinasi
• Parser/compiler

KONSEP DASAR

1. String(kata/untai) adalah suatu deretan terbatas (finite) dari symbol-simbol. 

• panjang string adalah jumlah simbol yang membentuk string tersebut
• String hampa/kosong adalah string dengan nol buah simbol 

contoh

• "a","b","c" adalah simbol-simbol
• "abcd" adalah suatu string
• "abcd" panjangnya 4

2. Dalam grammmar, dikenal symbol-symbol, yaitu : 

a.  Simbol terminal (token) 

Adalah symbol-simbol yang dilambangkan dengan huruf kecil, dan 

symbol-simbol tersebut sudah tidak dapat diturunkan lagi 

Contoh : a, b, c 

b.  Simbol non terminal(variable) 

Adalah symbol-simbol yang dilambangkan dengan huruf besar, dan 

symbol-simbol tersebut masih dapat diturunkan lagi 

Contoh : A, B, C 

c.  Simbol Awal (Start) 

Adalah symbol awal, biasanya dilambangkan dengan S

3. Aturan produksi dilambangkan dengan : 

α→β  : artinya α dapat diganti atau diturunkan dengan symbol β 

4. Derivasi kalimat (pembentukan kalimat) dilambangkan dengan : 

α⇒β  : artinya α adalah kalimat yang terdiri dari deretan symbol β 

Otomata

• input pada mesin otomata dianggap sebagai bahasa yang harus dikenali mesin
• selanjutnya mesin otomata membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak
• oleh karena itu mesin otomata dipakai untuk menghasikan bahasa yang aturannya ditentukan oleh aturan bahasa itu

contoh

• kita memiliki mesin sederhana menerima input kata dalam bahasa indonesia :
• bila mesin mendapat string input berikut
• aba : diterima
• abu : diterima
• abi : ditolak 
• sebuah string input diterima apabila mencapai state akhir/final state yang digambarkan dengan lingkaran ganda
• mesin tersebut memiliki 6 state {q0, q1, q2, q3, q4, q5} yang disebut himpunan state
• state awal q0
• state akhir {q3, q4}