Teori Bahasa dan Otomata

Kedudukan Teori Bahasa & Otomata pada Ilmu Komputer

Ilmu komputer memiliki dua komponen;

  1. Model & Gagasan mendasar mengenai komputasi
  2. Teknik rekayasa untuk perancangan sistem komputasi, meliputi perangkat keras dan perangkat lunak, khususnya penerapan rancangan dari teori

• Teori Bahasa & Otomata merupakan komponen ilmu komputer yang pertama. • Secara teoritis ilmu computer diawali dr sejumlah disiplin ilmu yang berbeda :

  • Ahli biologi mempelajari Neural Network

  • Insinyur Elektro mengembangkan Switching sebagai tool untuk mendisain hardware

  • Matematikawan bekerja berdasarkan logika

  • Ahli bahasa menyelidiki tata Bahasa untuk natural language

  • Teori bahasa dan otomata merupakan salah satu mata kuliah yang wajib di ilmu komputer. Cenderung bersifat teoritis tidak memuat hal-hal yang ‘praktis’ untuk diterapkan langsung dalam praktik.

  • Manfaat langsung dari mata kuliah teori bahasa dan otomata akan kita dapatkan ketika mempelajari mata kuliah Teknik Kompilasi.

  • Bahasa didalam kamus adalah suatu sistem yang meliputi pengekspresian gagasan, fakta, konsep, termasuk sekumpulan simbol- simbol dan aturan untuk melakukan manipulasinya. Bahasa bisa juga disebut sebagai rangkaian simbol-simbol yang mempunyai makna.
  • Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input. Otomata juga dianggap sebagai mesin otomatis (bukan mesin fisik) yang merupakan suatu model matematika dari suatu sistem yang menerima input dan menghasilkan output, serta terdiri dari sejumlah berhingga state.
  • Hubungan diantara 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 tidak.
  • Sebuah simbol adalah suatu entitas abstrak yang tidak kita definisikan secara formal, seperti halnya kita tidak mendefinisikan ‘titik’ dan ‘garis’ pada geometri. Huruf dan gigit adalah contoh symbol yang sering dipakai
  • Sebuat string (kata/untai) suatu deretan berhingga dari symbol-symbol. Contoh, ‘a’, ‘b’, ‘c’, adalah symbol-symbol dan ‘abcd’ adalah suatu string.
  • Panjang string adalah jumlah symbol yg membentuk string. Contoh, ‘abcd’ panjangnya 4, ‘asdfgh’ panjangnya 6.
  • Sebuah string kosong biasanya dinyatakan dengan Ꜫ, didefinisikan panjangnya = 0, atau |Ꜫ|=0 (pada beberapa buku symbol Ꜫ dinyatakan dengan ƛ

Misalnya, kita memiliki sebuah mesin sederhana yang menerima input kata dalam bahasa Indonesia, hal ini bisa dilihat pada gambar berikut ini.

Pada gambar di atas, bila mesin mendapat string input berikut. 1) “ada” : diterima 2) “adu” : diterima 3) “add” : ditolak

  • Sebuah string input diterima bila mencapai state akhir/final state yang disana digambarkan dengan lingkaran ganda. Mesin ini memiliki 6 state, {q0 ,q1, q2 ,q3 , q4 , q5 }, yang mana adalah 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}.

Hirarki Chomsky

  • Tata bahasa (grammar) bisa didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi.
  • Pada tahun 1959, seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat, yang disebut dengan hirarki Chomsky. Penggolongan tersebut bisa dilihat pada tabel berikut.

Secara umum tata bahasa (aturan produksi) dirumuskan sebagai : • α → β, yang berarti α menghasilkan β atau α menurunkan β. • Di mana α menyatakan simbol-simbol pada ruas kiri aturan produksi (sebelah kiri tanda ‘→’) dan β menyatakan simbol-simbol pada ruas kanan aturan produksi (sebelah kanan tanda ‘→’) • Simbol variabel / non terminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dst. • Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, dst.

  • Penggolongan (Hirarki Chomsky) berdasarkan pembatasan yang dilakaukan pada aturan produksinya.
  • Aturan produksi merupakan pusat dari tata bahasa, yang menspesifikan bagaimana suatu tata bahasa melakukan transformasi suatu string ke bentuk lainnya, dan melalui aturan produksi tersebut didefinisikan suatu Bahasa yang berhubungan dengan tata bahasa tersebut.

Tata Bahasa Regular

Aturan :

  • Simbol pada Sebelah kiri harus berupa sebuah simbol variabel
  • Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila ada terletak di posisi paling kanan.

Contoh : • A → b (Diterima) • a → B (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel) A → B (Diterima) • A → bC (Diterima) • A → Bc (Ditolak, karena simbol variabel pada sebelah kanan harus berada pada posisi paling kanan) • A → bcD (Diterima) • A → bCD (Ditolak, karena simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variabel) • Ab → c (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)

Tata Bahasa Bebas Konteks

Aturan : Simbol pada Sebelah kiri harus berupa sebuah simbol variabel

Contoh : • A → b (Diterima) • A → B (Diterima) • A → bC (Diterima) • A → Bc (Diterima) • A → BcD (Diterima) • A → AAA (Diterima) • a → b (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel) • Ab → c (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel) • AB → c (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)

Tata Bahasa Context Sensitive

Aturan :

  • Simbol pada Sebelah kiri harus minimal ada sebuah simbol variabel
  • Jumlah simbol pada ruas sebelah kiri harus lebih kecil atau sama dengan jumlah simbol pada ruas kanan

Contoh : • A → bc (Diterima) • Ab → cd (Diterima) • AB → CD (Diterima) • ABC → DE (Ditolak, karena jumlah simbol pada ruas sebelah kiri lebih bayak dari jumlah simbol pada ruas kanan) • Ab → cDe (Diterima) • bA → cd (Diterima) • a → b (Ditolak, karena simbol pada sebelah kiri harus minimal ada sebuah simbol variabel)

Tata Bahasa Unrestricted

Aturan :

  • Simbol pada Sebelah kiri harus minimal ada sebuah simbol variabel

Contoh : • Abcdef → g (Diterima) • aBCdE → GHIJKL (Diterima) • abcdef → GHIJKL (Ditolak, karena simbol pada sebelah kiri tidak ada sebuah simbol variabel)

  1. Tentukan apakah produksi-produksi berikut memenuhi aturan tata bahasa Regular a) A → b b) B → bdB c) B → C d) B → bC e) B → Ad f) B → bcdef g) B → bcdefg h) A → aSa i) A → aSS j) A → є
  1. Tentukan apakah aturan produksi-produksi berikut memenuhi aturan tata bahasa bebas konteks a) A → aSa b) A → Ace c) A → ab d) A → є e) B → bcdef f) B → bcdefG g) A → aSa h) A → aSS
  1. Tentukan apakah produksi-produksi berikut memenuhi aturan tata bahasa context sensitive a) B → bcdefG b) A → aSa c) A → aSS d) A → BCDEF e) Ad → dB f) A → є g) AB → є h) ad → b i) ad → є j) abC → DE k) abcDef → ghijkl l) AB → cde m) AAA → BBB
  1. Tentukan apakah produksi-produksi berikut memenuhi aturan tata bahasa unrestricted a) A → є b) AB → є c) ad → b d) ad → є e) abC → DE f) AB → cde g) e → a h) ABCDEFG → h i) bA → CDEFGH
Reload?