KONSEP BAHASA DAN OTOMATA

                   Sebuah simbol adalah  suatu entitas abstrak yang tidak kita definisikan secara formal, seperti halnya kita tidak mendefinisikan 'titik' dan 'garis' pada geometri. Huruf dan digit adalah contoh dari simbol yang sering dipakai. Sebuah string (kata/untai) adalah suatu deretan berhingga dari simbol - simbol. Sebagai contoh, 'a', 'b','c' adalah suatu string. Pada konsep ini kita akan menggunakan istilah string dan untai bergantian. Panjang string disini adalah jumlah simbol yang membentuk string tersebut. Contoh :

'abad' panjangnya 4

asdfgh panjangnya 6

                    Sebuah string kosong, biasanya dinyatakan dengan Ɛ, didefinisikan panjangnya = 0, atau

 | Ɛ | = 0 (pada beberapa buku, simbol untuk Ɛ dinyatakan dengan λ). Suatu alphabet adalah hompunan berhingga dari simbol - simbol.

                    Pada umumnya kita mengenal bahasa alami, seperti bahasa inggris atau indonesia. Bahasa di definisikan di dalam kamus adalah suatu sistem yang meliputi pengekspresian gagasan, fakta, konsep, termasuk sekumpulan simbol - simbol  dan aturan untuk melakukan manipulasinya. Sebuah bahasa adalah himpunan string - string dari simbol  untuk satuan alphabet. Karena sebuah bahasa adalah kumpulan dari string - string, kita bisa mempunyai sebuah  bahasa yang tidak terdiri dari string - string, yaitu bahasa kosong, yang dinotasikan seperti kita menuliskan himpunan kosomg, ᴓ. Bahasa kosong berbeda dengan bahasa yang terdiri dari string kosong { Ɛ }.  Bahasa bisa juga disebut sebagai rangkaian  simbol - simbol yang mempunyai makna.

                    Untuk memodelkan hardware dari komputer diperkenalkan otomata. Otomata adalah sebuah bentuk yang memilikik fungsi - fungsi dari komputer digital. Menerima input menghasilkan output, bisa meiliki penyimpanan sementara, dan mampu membuat keputusan  dalam mentransformasikan input ke output. Sebuah bahasa formal adalah sebuah abstraksi terdiri dari himpunan simbol - simbol dan aturan - aturan  yang mana simbol - simbol tersebut dikombinasikan kedalam entitas yang disebut kalimat. Meskipun bahasa formal  yang dipelajari disini lebih sederhana dari bahasa pemrograman, mereka mempunyai banyak hal yang penting. kita bisa mempelajari banyak tentang bahasa pemrograman dari bahasa formal.

                    Otomata merupakan suatu system yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yang lalu, dan dapat pula dianggap sebagai memori mesin. input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya mesin otomata membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak. Sehingga mesin otomata dapat dipakai untuk menghasilkan bahasa yang aturannya ditentukan oleh aturan bahasa itu.

                     Misalnya, kita memiliki sebuah mesin sederhana yang menerima input kata dalam bahasa indonesia, hal ini dilihat pada gambar dibawah.

Pada gambar tersebut, bila mesin mendapat string input berikut :

• ada : diterima,
• adu : diterima,
• add : ditolak.

                  Sebuah string input diterima apabila mencapai state akhir/final state, yang di situ digambarkan dengan lingkaran akhir di sebelah kanan. Mesin memiliki 6 state {q0,q1,q2,q3,q4,q5}, yang mana lingkaran himpunan state yang ada pada mesin  itu. state awal dari mesin adalah q0. {q3,q4} adalah himpunan state akhir/final. sedangkan himpunan simbol input adalah {a,d,u}. penjelasan lebih lanjut secara formal dari suatu sistem otomata bisa dilihat dari postingan selanjutnya.