Pengantar Teori Bahasa dan Otomata

A. Pengantar Teori Bahasa dan Otomata

1. Bahasa

Bahasa adalah rangkaian simbol - simbol yang mempunyai makna

2. Otomata

Otomata merupakan sebuah sistem yang terbangun dari sejumlah State yang menyatakan informasi mengenai input. Otomata seringkali dianggap sebagai sebuah mesin otomatis (bukan mesin fisik) yang merupakan mpde; matematika dari sistem yang menerima input dan menghasilkan output.

3. Hubungan Bahasa dan Otomata    

Bahasa Dijadikan sebagai input oleh mesin otomata, lalu mesin otomata akan membuat keputusan apakah input tersebut diterima atau ditolak

 

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

1.ada : diterima 

2.adu : diterima 

3.add : ditolak

Penjelasan : 

1. Sebuah string input diterima bila mencapai state akhir / final state yang pada contoh diatas digambarkan dengan lingkaran ganda. 

2. Mesin ini memiliki 6 state yaitu { q0, q1, q2, q3, q4, q5 } yang merupakan himpunan state yang ada pada mesin tersebut. 

3. State awal dari mesin adalah q0. 

4. { q3, q4 }adalah himpunan state akhir atau final state. 

5. Sedangkan himpunan simbol input adalah {a, d, u}. 

B. Konsep Teori Bahasa dan Otomata

1. Empty String (Null String)

adalah string yang tidak mengandung simbol apapun.

2. Regular Expression 
adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi

C. Hierarky Chomsky

1. Secara umum tata bahasa dirumuskan sebagai berikut : 

a → b, yang berarti a menghasilkan b atau a menurunkan b.

2. Simbol variabel / non terminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dst.

3. Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, dst

D. Hierarky Chomsky Type 0 / Unrestricted / Natural Language

Aturan : 

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

2. Tidak ada batasan pada aturan produksinya.

Misal : Ab → cDe (diterima) 

            AB → Cd (diterima) 

            abc → DEf (ditolak) 

E. Hierarky Chomsky Type 1 / Conteks Sensitive

Aturan :

1. Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variable

2. Panjang string pada ruas kiri ≤ panjang string pada ruas kanan
Misal : Ab → DeF (diterima) 

            CD → eF (diterima) 

exception : S → ε (diterima) 

            ABC → DE (ditolak) 

F. Hierarky Chomsky Type 2 / Bebas Konteks/ Context Free

Aturan : 

1. Simbol pada Sebelah kiri harus berupa sebuah simbol variable

Misal : B → CDeFG (diterima) 

            D → BcDe (diterima) 

            a → b (ditolak)

            Ab → F (ditolak)

G.  Hierarky Chomsky Type 3 / Reguler Grammer

Aturan : 

1. Simbol pada Sebelah kiri harus berupa sebuah simbol variabel

2. 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)