Teori Bahasa Dan Otomata serta Hirarki Chomsky || Nur Anisah Fadhilah - 202131020

 

Institut Teknologi PLN Jakarta

Dosen : DINE TIARA KUSUMA, S.T., M.Kom

PENJELASAN TEORI BAHASA DAN OTOMATA SERTA HIRARKI CHOMSKY

Bahasa 

Bahasa disebut sebagai rangkaian simbol - simbol yang mempunya makna.

Otomata 

• Otomata merupakan suatu sistem yang terdiri atas sejumlah state, di mana 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

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. 

Penjelasan : 

• Sebuah string input diterima bila mencapai state akhir (final state) yang ada pada contoh disamping digambarkan dengan lingkaran ganda.
• Mesin ini memiliki 6 state yaitu q0, q1, q2, q3, q4, q5. State awal yaitu q0. q3 dan q4 adalah state akhir, sedangkan simbol input nya yaitu a,  d, u. 

1. ada : diterima
2. adu : diterima
3. add : ditolak

Konsep Teori Bahasa & Otomata 

• Teori Bahasa adalah konsep-konsep pada "string alpabet - dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (bahasa).
• Alpabet adalah himpunan simbol (karakter) tidak kosong dan berhingga Alpabet dilambangkan dengan Zigma.
• String adalah deretan simbol dari alphabet 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 bukan pada alpabet dan pengulangan. Kemunculan simbol dihitung.

Contoh :

|c| = 0

|a| = 1

|aa| = 2

|aaa| = 3

|aaab| = 4

• Empty String (null string) adalah string yang tidak mengandung simbol apapun. Lambang nya ɛ atau 𝛌.

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

- Concatenation (Penyambungan)

  Contoh : 'a' o 'b' = 'ab'

- Superscript (Perkalian)

  Contoh : V o V = VV = V2

- Kleene Closure (String Tanpa Simbol)

  Contoh :

  ɛ mempunyai sifat identitas, yaitu :

  ɛ o x = x

  x o ɛ = x

- Positif Closure (Tidak Ada String Kosong Didalamnya)

  Vt = V1 U V2 U V3 U ......

Hirarki Chomsky

Secara umum tata bahasa dirumuskan sebagai berikut :

ɑ => β, yang berarti ɑ menghasilkan β, atau ɑ menurunkan β.

• 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.

Contoh Aturan Produksi

- T => ɑ

dibaca "T menghasilkan a"

- E => T | T + E

dibaca "E menghasilkan T" atau "E menghasilkan T dan E"

- Simbol | menyatakan '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.

Contoh :

Abc => De (diterima)

ABC => b (diterima)

abc => GHI (ditolak, karena simbol pada sebelah kiri tidak ada sebuah simbol variabel)

• Tipe 1 / Konteks Sensitive

Aturan :

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

- Panjang string pada ruas kiri <= panjang string pada ruas kanan. |ɑ| <= |β|.

Contoh :

Ab => DeF (diterima)

CD => eF (diterima)           exception : S => ɛ (diterima)

ABC => DE (ditolak, karena jumlah simbol pada ruas sebelah kiri lebih banyak dari jumlah simbol pada ruas kanan)

• Tipe 2 / Bebas Konteks / Context Free

Aturan :

- Simbol pada sebelah kiri harus berupa sebuah simbol variabel

Contoh :

B => CDeFG (diterima)

D => BcDe (diterima)

a => b (ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)

• Tipe 3 / Reguler Aturan

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 => e (diterima)

A => fgh (diterima)

A => eH (diterima)

C => D (diterima)

A => Bc (ditolak, karena simbol variabel pada sebelah kanan harus berada pada posisi paling kanan)