Penjelasan Teori Bahasa Dan Otomata serta Hirarki Chomsky

 Asssalamualaikum Warrahmatullahi Wabarrakatuh

Halo semuaa !!.....👋😊

---

Selamat datang di blog saya, perkenalkan saya Rina Setiyaningsih dengan NIM 202131022 , Mahasiswi Informatika dan berkuliah di Institut Teknologi PLN Jakarta.

Disini saya akan membahas ulang materi yang sudah disampaikan Bu DINE TIARA KUSUMA ,S.T., M.Kom. Pada pertemuan di hari Rabu,15 maret 2023, materi yang disampaikan adalah pembahasan tentang teori Bahasa dan Otomata dan Hirarki Chomsky

Bahasa

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

Otomata

·      Otomata merupakan suatu system 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 suata system yang menerima input dan menghasilkan input.

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.

Ilustrasi gambar mesin sederhana

Penjelasan dari gambar

·      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 himpunan  symbol input {a,d,u}

Konsep Teori Bahasa dan Otomata

·      Teori Bahasa adalah konsep-konsep pada “string alpabet” dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (Bahasa).

·      Alpabet adalah himpunan symbol (karakter) tidak kosong dan berhingga. Alpabet dilambangkan dengan sigma 

·      String adakah deretan symbol dari alpabet dimana perulangan symbol diijinkan.

Contoh:

V= {a,b,c,d}

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

·      Panjang string adalah jumlah symbol di dalam string bukan pada alpabet dan pengulangan, kemunculan symbol dihitung. Panjang string dilambangkan /w/

 

Contoh :

|e| = 0

| a | = 1

| aa | = 2

| aaa | = 3

| aaab | = 4

 

·  Empty string (null string) adalah string yang tidak mengandung symbol apapun. Lambangnya atau lamda

·    Regular experession adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi :

o   Concatenation (penyambungan)

Contoh :

‘a’ o ‘b’ = ‘ab’

o   Superscript (perkalian)

Contoh :

VoV = VV =V²

o   Kleene closure (String Tanpa Simbol)

e mempunyai sifat identitas , yaitu :

e o x = x

x o e = x

o   positif closure (tidak ada string kosong didalamnya)

 

Vt = V¹ U V² U V³ U…

Hirarki Chomsky 

·      secara umum tata bahasa dirumuskan sebagai berikut :

·      a -> b , yang berarti a menghasilkan b atau a menurunkan b.

·     Symbol variabel / non terminal adalah symbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A,B,C,dst.

·      Symbol terminal adalah symbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a,b,c,dst.

CONTOH ATURAN PRODUKSI

·      T -> a

Dibaca “T menghasilkan a”

 

·      E -> T | T + E

Dibaca  “E menghasilkan T “ atau “ E menghasilkan T  dan E”

 

Symbol | menyatakan ‘atau’, digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama.

 

Tipe 0 / Unrestricted / Natural Language

Aturan :

·      Symbol pada ruas sebelah kiri harus minimal ada sebuah symbol variabel

·      Tidak ada Batasan pada aturan produksinya.

·      Misal :             

o   Abc  -> De  (diterima)

o   ABC -> b    (diterima)

o   Abc  -> GHI (ditolak,karena symbol pada sebelah kiri tidak ada sebuah symbol      variabel)

 

Tipe 1/ Conteks Sensitive

Aturan :

·      Symbol pada ruas sebelah kiri harus minimal ada sebuah symbol variable

·    Panjang string pada ruas kiri   (kurang dari sama dengan) panjang string pada ruas kanan

  

Misal:

Ab  -> DeF (diterima)

CD -> eF(diterima)

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

Tipe 2 / Bebas Konteks / Context Free

Aturan :

·      Simbol pada sebelah kiri harus berupa sebuah symbol variable 

Misal :

 

B  -> CDeF (diterima)

D -> BcDe (diterima)

A -> b (ditolak,karena symbol pada sebelah kiri harus berupa sebuah symbol variabel)

Tipe 3 / Reguler Aturan :

Aturan :

·      Symbol pada sebelah kiri harus berupa sebuah symbol variabel

·      Symbol pada sebelah kanan maksimal hanya memiliki sebuah symbol variabel dan bila ada terletak diposisi paling kanan.

·      Misal :

A -> e (diterima)

A ->fgh (diterima)

A -> eH (diterima)

C -> D (diterima)

A -> Bc (ditolak, karena symbol variable pada berada pada posisi sebelah kanan harus berada pada paling kanan)

 

Kesimpulan dari beberapa tipe Hirarki Chomsky :

Jika syarat dan aturan pada tipe 3 terpenuhi, maka hirarki Chomsky tipe 0 , tipe 1, tipe 2 sudah pasti terpenuhi aturan nya dan dapat diterima.

Berikut pembahasaan materi pada 15 maret 2023 .Sekian yang bisa saya sampaikan, Mohon maaf bila ada salah pengetikan.

Terimakasih, Sampai bertemu di penyampaian materi berikutnya👐😊

Wassalamualaikum Warrahmatullahi Wabarrakatuh