Pengantar Teori Bahasa&Otomata(Teori Bahasa&Otomata)

Selamat dini hari para pembaca..

ntah kenapa suka sekali ngeposting tulisan di jam jam menjelang subuh gini, rasa rasa gimana gitu yah.. nah saya tau ini garing saya hanya menoba menghibur hahaha oke kali ini saya akan mencoret coret blog saya dengan tema 

PENGANTAR TEORI BAHASA & OTOMATA

disimak yaa...

Bahasa di dalam kamus adalah suatu sistem yang meliputi pengekspresian gagasan, fakta, konsep, termasuk sekumpulan simbol-simbol dan aturan untuk dilakukan manipulasi.

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

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.

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 berikut ini :

Pada gambar di samping, bila mesin mendapat string input berikut :

ada : diterima 

adu : diterima 

add : ditolak

Penjelasan :

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 simbol input adalah {a, d, u}.

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 digunakan untuk membentuk kata-kata (string-string) di bahasa. Bahasa dimulai dengan alpabet. Alpabet dilambangkan dengan Σ

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 bukan pada alpabet dan pengulangan  kemunculan simbol dihitung. 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 atau

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)

Concatenation (Penyambungan)

Penyambungan dilakukan pada 2 karakter atau lebih membentuk 1 barisan karakter (string simbol).

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

Superscript (Perkalian)

Penyambungan dapat dianggap sebagai perkalian karena biasanya penulisannya adalah bila x dan y string, maka x o y adalah xy. sehingga pemangkatan dapat digunakan

Contoh :
VoV = VV = V2 ----> Panjang string = 2

Kleene closure (String Tanpa Simbol)

adalah string pada V, termasuk string kosong dimana ε string kosong (string tanpa simbol) 

ε mempunyai sifat identitas, yaitu:
ε o x = x
x o ε = x

Positif Closure (Tidak Ada String Kosong Didalamnya)

V+ = V1 U V2 U V3 U ... 
adalah himpunan string pada V, tidak ada string kosong didalamnya.

V0 = {ε}
adalah himpunan yang isinya hanya string kosong, dimana String kosong ε tidak sama dengan himpunan kosong 

HIRARKI CHOMSKY

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 dirumuskan sebagai berikut :

α → β, 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.

CONTOH ATURAN PRODUKSI 

T → a   

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 1/ Conteks Sensitive

Aturan :

Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variable

Panjang string pada ruas kiri ≤ panjang string pada ruas kanan 

|α | ≤ |β|.

Misal :

Ab  → DeF (diterima)

CD  → eF (diterima)

exception : S → ε (diterima)

ABC → DE  (ditolak, karena jumlah simbol pada ruas sebelah kiri

lebih bayak dari jumlah simbol pada ruas kanan)

Tipe 2 / Bebas Konteks/ Context Free

Aturan :

Simbol pada Sebelah kiri harus berupa sebuah simbol variable

Misal :

B  → CDeFG  (diterima)

D → BcDe (diterima)

a  → b  (Ditolak, karena simbol pada sebelah kiri harus

berupa sebuah simbol variabel)

Tipe 3/ RegulerAturan :

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.

Misal : 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)

Aturan produksi seperti :

ε → Abd

bukan aturan produksi yang legal, karena simbol ε tidak boleh berada pada ruas kiri  

Aturan produksi yang ruas kirinya hanya memuat simbol terminal saja, seperti : 

a  →  bd

ab → bd

bukan aturan produksi yang legal, karena ruas kiri juga harus memuat simbol yang bisa diturunkan.

semoga bermanfaat :)