Teori Bahasa & Otomata

• Pengantar Tata Bahasa dan Otomata

1. Bahasa bisa  juga disebut sebagai rangkaian simbol simbol yang mempunyai makna 
2. Otomata sebuah sistem yang terdiri atas sejumlah state yang aman state menyatakan informasi mengenai input
3. Otomata juga diangap sebagai mesin otomatis ( bukan mesin fisik) yang merupakan suatu model matematika dari suatu sistem yang menerima input dan menghasilkan output
4. Hubungan diantara bahasa dan otomata adalah bahsa dijadikan sebagai input oleh suatu mesin otomata, selanjutnya mesin otoamata akan membaut keputuan yang mengindikasikan apakah input itu diterima atau ditolak

• Konsep Bahasa

1. Bahasa adalah himpunan string-string dari simbol simbol untuk suatu alphabet atau rangkaian simbol yang mempunyai makna
2. sementara string adalah deretan simbol dari alphabet dimana perulangan simbol diijinkan
3. bahasa kosong adalah bahsa yang tidak terdiri dari string string , dinotasikan dengan Ø  

• Empty String

1. Empty string adalah string yang tidak mengandung simbol apapun, 
2. Regular expression adalah cara untum mengekspresikan bahasa dengan hanya menggunakan operasi  :
   - Concatenation ( Penyambungan ) 
   - Superscript ( Perkalian )
   - Kleene Closure ( String tanpa simbol )
   - Positif Closure (tidak ada string kosong didalamnya)

• Hirariki Chomsky

1. Secara umum tatabahasa dirumuskan sebagai berikut :
   - a -> b yang berarti a menghasilkan b atau a menurunkan b. ( a =  α b =  λ )
   - Simbol variabel / non terminal adalah simbol yang masih bisa diturunkann 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 adalah :

        - 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 mempynyai ruas kiri yang sama

• Tipe 0

1. Aturan : 

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

- Tidak ada batasan pada aturan produksinya.

Misal : Abc ->De ( diterima)

  Abc -> b ( diterima)

  abc  -> Ghi ( ditolak, karena simbol pada sebelah kiri tidak ada sebuah simbol variabel)

• Tipe 1 

1. Aturan :

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

- Panjang string ruas kiri lbih panjang string pada ruas akanan

Contoh : 

AB -> CD ( diterima ) 

        ABC -> De ( ditolak)

• Tipe 2 

1. Aturan : 

- Simbol pada sebelah kiri harus berupa simbol variable

Contoh : 

Ab -> Ac ( ditolak) karena harus sebuah (satu)  simbol variabel

• Tipe 3 

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