Teori Bahasa Automata

Teori Bahasa
Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama.

Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima(accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.



Beberapa Pengertian Dasar
•Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai | w | dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka | w | = 4.
• String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol ε (atau ^) sehingga |ε |= 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol




Konsep Dasar
1. Dalam pembicaraan grammar, anggota alfabet dinamakan simbol terminal
atau token.
2. Kalimat adalah deretan hingga simbol-simbol terminal.
3. Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga
kalimat.
4. Simbol-simbol berikut adalah simbol terminal (VT) :
• huruf kecil alfabet, misalnya : a, b, c
• simbol operator, misalnya : +, −, dan ×
• simbol tanda baca, misalnya : (, ), dan ;
• string yang tercetak tebal, misalnya : if, then, dan else.
5. Simbol-simbol berikut adalah simbol non terminal (VN) :
• huruf besar alfabet, misalnya : A, B, C
• huruf S sebagai simbol awal
• string yang tercetak miring, misalnya : expr dan stmt.
6. Huruf besar akhir alfabet melambangkan simbol terminal atau non
terminal, misalnya : X, Y, Z.
7. Huruf kecil akhir alfabet melambangkan string yang tersusun atas simbol-simbol
terminal, misalnya : x, y, z.


Grammar dan Klasifikasi Chomsky
Grammar G didefinisikan sebagai pasangan 4 tuple : VT , VN , S, dan Q, dan dituliskan sebagai G(VT , VN  , S, Q), dimana :
VT : himpunan simbol-simbol terminal (atau himpunan token -token, atau alfabet)
VN : himpunan simbol-simbol non terminal
S ∈ V N : simbol awal (atau simbol start)
Q : himpunan produksi

•Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β),

1. Grammar tipe ke-0 : Unrestricted Grammar (UG)

      •Ciri : α, β ∈ (VT | VN)*, |α|> 0

      • Tidak ada batasan pada aturan produksi

      •Contoh:  Abc → Do

2. Grammar tipe ke-1 : Context Sensitive Grammar (CSG)

      • Ciri : α, β ∈ (VT | VN)*, 0 < |α| ≤ |β|

      •Panjang string ruas kiri harus < (lebih kecil) atau = (sama dengan) ruas kanan

      •Contoh: Ab → DeF CD → eF

3. Grammar tipe ke-2 : Context Free Grammar (CFG)

      • Ciri : α ∈ VN , β ∈ (VT | VN)*

      •Ruas kiri haruslah tepat satu symbol variabel, yaitu simbol non terminal

      • Contoh : B → CDeFg

                      D → BcDe

4. Grammar tipe ke-3 : Regular Grammar (RG)

     • Ciri : α ∈ VN, β ∈ {VT, VT  VN} atau α ∈ V N, β ∈ {VN, VT  VN}

     •Mengingat ketentuan simbol-simbol (hal. 3 no. 4 dan 5), ciri-ciri RG sering dituliskan sebagai : α ∈ V N, β ∈ {a, bC} atau α ∈ V N, β ∈ {a, Bc}

     •Ruas kanan hanya memiliki maksimal satu symbol non terminal 

     •Contoh  : A → e

  A → efg

    A → efgH

    C → D