Pengenalan Teori Bahasa & Otomata

  Apa Itu Teori Bahasa Dan 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 model matematika dari suatu sistem yang menerima input dan menghasilkan output.

    Hubungan diantara 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.

Contoh penerapan mesin otomata, misalnya kita akan memodelkan mesin otomata yang hanya dapat menerima inputan dalam bahasa inggris. Apabila digambarkan pemodelan bahasanya akan menjadi : 

Pada gambar 1.1 diatas merupakan mesin otomata yang hanya dapat menerima inputan berupa bahasa inggris, jika mesin mendapatkan string inputan :
     ~ dengan : di tolak
     ~ deny : diterima
     ~ dentist : diterima
suatu string dikatakan diterima apabila mencapai state akhir(lingkaran ganda) untuk kasus ini ada pada q7 dan q11. State awal selalu diawali oleh panah tanpa inputan (state q0). 

Konsep Teori Bahasa Dan Otomata

- String adalah deretan simbol dari alvabet dimana perulangan simbol diijinkan.
   Contoh :
   V = {a,b,c,d}
   String pada alvabet V antara lain -> 'a','abcd','bbba'

- Panjang String adalah jumlah simbol simbol di dalam string bukan pada alvabet 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 𝝀

- Reguler Expression adalah cara untuk mengespresikan bahasa dengan hanya menggunakan operasi :

Concatenation (Penyambungan)

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

Superscript (Perkalian)
VoV = VV = V²

Kleene closure (Stting Tanpa Simbol)
∈ mempunyai sifat identitas, yaitu:
∈ o x = x
x o ∈ = x

Positif closure (Tidak Ada String Kosong Didalamnya)

V⁺ = V¹ U V² U V³ U ...

Hirarki Chomsky

Contoh Aturan Produksi 
> T ⇾ 𝑎
    dibaca "T menghasilkan a"
> T ⇾ 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.

1. Recursively Enumerable (Level/Tipe 0)
   Mesin Automata : Mesin Turing.
   Terlalu umum dan tidak terbatas untuk mendeskripsikan sintaks dari bahasa pemrograman atau bahasa alami.
   Aturan :
   
• Simbol ruas sebelah kiri harus minimal ada sebuah simbol variabel.
• Tidak ada batasan pada aturan produksi.
2. Context-Sensitive (Level/Tipe1)
   Mesin Automata: Linier Bounded Automata.
   Level tertinggi yang dapat diprogram, menghasilkan bahasa sensitif konteks. Mereka memiliki aturan bentuk α A β → α γ β dengan A sebagai non-terminal dan α, β, γ sebagai string terminal dan non-terminal. String α, β boleh kosong, tetapi γ harus tidak kosong.
   Aturan :
   
• Simbol pada ruas sebelah kiri harus minimal ada sebuah variabel.
• |a| ≤ |b| artinya ruas sebelah kiri tidak lebih besar dari ruas sebelah kanan.
3. Context-Free (Level/Tipe 2)
   Mesin Automata : Push Down Automata.
   Menghasilkan bahasa tanpa konteks, kategori yang sangat menarik bagi praktisi NLP . Di sini semua aturan mengambil bentuk A → β, di mana A adalah simbol non-terminal tunggal dan β adalah string simbol.
   Aturan :
   
• Simbol sebelah kiri harus simbol variabel.
4. Regular Grammar (Level/Tipe 3)
   Mesin Automata : Finate State Automata.
   Set paling ketat, mereka menghasilkan bahasa biasa. Mereka harus memiliki satu non-terminal di sisi kiri dan sisi kanan yang terdiri dari satu terminal atau terminal tunggal diikuti oleh satu non-terminal.
   Aturan :
   
   • Simbol sebelah kiri harus berupa simbol variabel.
   • Simbol sebelah kanan maksimal hanya memiliki simbol variabel dan bila ada terletak di paling kanan.