Pengantar Teori Bahasa dan Otomata

Bahasa

Bahasa bisa juga disebut sebagai rangkaian simbol-simbol yang mempunyai makna

Otomata

• Otomata merupakan suatu sustem yang terdiri atas sejumlah state, dimana state menyatakan informasi mengenai input.
• Otomata juga dianggap sebagai mesin otomatis (bukkan mesin fisik) yang merupakan suatu model matematika daru suatu sistem yang menerima input dan menghasilkan output

Bahasa & Otomata

Hubungan di antara bahasa dan otomata adalah bahasa dijadikan sebagai input oleh suatu mesin otomata, selanjutnya mesin otomata akan membuat keputusan yang mengindikasikan apakah input itu diterima atau ditolak.

Misalnya, kita memiliki sebuah mesin sederhana yang menerima input kata dalam bahasa indonesia, hal ini bisa dilihat pada gambar disamping. Pada gambar disamping, bila mesin mendapat string input berikut:

1. ada : diterima

2. adu : diterima

3. add : ditolak

Penjelasannya adalah:

• Sebuah string input diterima bila mencapai state akhir / final state yang pada contoh diatas digambarkan dengan lingkaran ganda.
• Mesin ini memiliki 6 state yaitu { q0, q1, q2, q3, q4, q5 } yang merupakan himpunan state yang ada pada mesin tersebut.
• State awal dari mesin adalah q0.
• { q3, q4 } adalah himpunan state akhir atau final state.
• Sedangkan simbol input adalah { a, d, u }.

Teori Bahasa adalah konsep-konsep pada "string alphabet" dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (bahasa).

Alpabet adalah himpunan simbol (karakter) tidak kosong dan berhingga. Alpabet dilambangkan dengan ∑

Konsep Teori Bahasa dan Otomata

• String adalah deretan simbol dari alpabet dimana perulangan simbol diijinkan. Contoh: 

            V = {a,b,c,d}

            String pada alpabet V antara lain -> 'a', 'abcd','bbba'

• Panjang String adalah jumlah simbol di dalam string pada alpabet dan pengulangan. kemunculan simbol dihitunh. Panjang string dilambangkan |w|. Contoh:

            |ε| = 0

            |a| = 1

            |aa| = 2

            |aaa| = 3

            |aaab| = 4

Empty String (null string) adalah string yang tidak mengandung simbol apapun. Lambangnya e atau l

Regular Expression adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi:

• Concatenation (Penyambungan)
• Superscript (Perkalian)
• Kleene Closure (String Tanpa Simbol)
• Positif closure (Tidak Ada String Kosong Didalamnya)