Pada kali ini , saya akan memposting materi dari mata kuliah Teori Komputasi dan Bahasa Formal yang diajarkan di Jurusan Teknik Informatika UNPAS . yaitu mengenai Teori Bahasa dan Automata . Berikut adalah penjelasan mengenai apa itu Teori bahasa dan automata.

Teori Bahasa dan Automata

Teori Bahasa

Teori bahasa membicarakan bahasa formal (formal languange) , 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 yang berbeda . Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya . Bahasa manusia bersifat sebaliknya . grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat . Dalam pembicaraan selanjutnya , bahasa formal akan disebut bahasa saja

Automata

Automata adalah mesin abstrak yang dapat mengenali , menerima atau membangkitkan sebuah kalimat dalam bahasa tertentu . Automata berkaitan erat dengan teori bahasa formal . Selain itu juga ada beberapa hal yang berkaitan dengan Otomata , yaitu Grammar . Grammar adalah bentuk abstrak yang dapat diterima untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu .

Konsep Bahasa dan Automata

Ada beberapa konsep - konsep bahasa yang ada di dalam Teori Automata , yaitu :

Anggota alfabet dinamakan simbol terminal
Kalimat adalah deretan hingga simbol - simbol terminal
Bahasa adalah himpunan Kalimat - Kalimat.
String adalah suatu deretan berhingga dari simbol - simbol , contoh : 'a','b','c' adalah simbol dan 'abc' adalah sebuah string.
Simbol -Simbol terminal . Seperti : Huruf kecil (a,b,c) , Simbol Operator (+ dan *) , Simbol tanda baca ( , dan ; ) dan String yang bercetak tebal . Contohnya adalah if , then dan else.
Simbol - simbol non terminal / Variabel .Seperti : Huruf besar (A, B, C) , huruf S sebagai simbol awal , String yang tercetak miring (expr)
Huruf yunani melambangkan string yang tersusun atas simbol - simbol terminal atau simbol - simbol non terminal atau campuran keduanya , misalnya pada gambar di bawah ini :

Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.
Derivasi adalah proses pembentukan sebuah kalimat atau sentensial . Sebuah derivasi dilambangkan sebagai berikut :

Sifat - Sifat Automata

Berikut adalah sifat - sifat dari Automata :

Kelakuan mesin bergantung pada rangkaian masukan yang diterima mesin tersebut.
Setiap saat , mesin dapat berada pada suatu status tertentu dan dapat berpindah ke status baru karena adanya perubahan input.
Rangkaian input (diskrit) pada mesin automata dapat dianggap sebagai bahasa yang harus "dikenali" oleh sebuah otomata . setelah pembacaan input selesai , mesin automata kemudian membuat suatu "keputusan".