Pertemuan 1 : Pengantar Teori Bahasa & Otomata

 Pengantar Teori Bahasa & Otomata

Pengertian

Teori Bahasa dan Otomata merupakan percabangan dari ilmu komputer yang berkaitan dengan bagaimana cara merancang model abstrak perangkat komputer yang mengikuti urutan langkah-langkah yang telah ditentukan secara otomatis.

Secara harfiah, teori bahasa merupakan konsep-konsep pada "string alphabet" dalam penyambungan karakter-karakter alphabet untuk membentuk suatu makna (bahasa).

Alphabet adalah himpunan simbol (karakter) tidak kosong dan berhingga. Alpabet dilambangkan dengan Σ (Sigma).

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.

Contoh penerapan bahasa dan otomata dalam keseharian :

• ATM
• Vending Machine
• Kartu E-Money

Misalnya, kita memiliki sebuah mesin sederhana yang menerima input kata. Dalam Bahasa Indonesia seperti pada ilustrasi. Maka bisa disimpulkan string input sebagai berikut :

    1. ada: diterima

    2. adu: diterima

    3. add: ditolak

Hierarki Chomsky

Secara umum tata bahasa dirumuskan sebagai berikut :

α → β artinya α menghasilkan β atau α menurunkan β

Simbol variable / non terminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dan sebagainya

Simbol terminal adalah simbol yang tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, dan sebagainya

Contoh aturan produksi

-          T à a

dibaca “T menghasilkan a”

-          E à T | T + E

dibaca “E menghasilkan T atau E menghasilkan T dan E”

Simbol “ | “ dibaca atau, digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama.

Tipe 0 / Unrestricted / Natural Language

Aturan :

-        Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel.

-        Tidak ada batasan pada aturan produksinya :

Misal :      Abc à De        (diterima karena ada variable A)

                   ABC à e           (diterima karena syarat hanya sebuah variable, jika lebih boleh)

                   abc à DEF       (ditolak karena tidak ada variable di ruas kiri)

Tipe 1 / Context Sensitive

Aturan :

-        Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel.

-        Panjang string pada ruas kiri harus ≤ panjang string pada ruas kanan.

Misal :          Ab à De       (diterima karena panjang string ruas kiri masih sama dengan ruas kanan)

                     A à Fg          (diterima karena panjang string ruas kiri kurang dari ruas kanan)

                     ABC à De    (ditolak karena panjang string ruas kiri kurang dari ruas kanan)

Tipe 2 / Konteks Bebas / Free Context

-        Simbol pada ruas sebelah kiri harus berupa sebuah simbol variabel.

Misal :           A à ABcDe         (diterima karena ruas kiri hanya 1 variabel)

                      H à FgHi             (diterima karena ruas kiri hanya 1 variabel, ruas kanan bebas)

                      Ab à DeF             (ditolak karena ruas kiri panjang stringnya 2 dan terdapat simbol)

Tipe 3 / Reguler

Aturan :

-        Simbol pada ruas sebelah kiri harus berupa sebuah simbol variabel.

-        Ruas kanan hanya boleh memiliki sebuah variabel dan letaknya harus paling kanan.

Misal :       A à e                 (diterima, ruas kiri 1 variabel dan ruas kanan tidak lebih dari 1 variabel)

                  B à ghiJ            (diterima , ruas kiri 1 variabel dan ruas kanan hanya ada 1 variabel)

                  C à Hi               (ditolak karena posisi variable ruas kanan tidak terletak di paling kanan)