Bahasa dan 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. Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya. Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja. Automata Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

Konsep Dasar

Anggota alfabet dinamakan simbol terminal.

*Kalimat adalah deretan hingga simbol-simbol terminal.

*Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.

*Simbol-simbol berikut adalah simbol terminal :

huruf kecil, misalnya : a, b, c ü simbol operator, misalnya : +, -, dan ´ ü simbol tanda baca, misalnya : (, ), dan ; ü string yang tercetak tebal, misalnya : if, then, dan else. · Simbol-simbol berikut adalah simbol non terminal /Variabel : ü huruf besar, misalnya : A, B, C ü huruf S sebagai simbol awal ü string yang tercetak miring, misalnya : expr · Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : a, b, dan g

Finite State Automata

Finite state automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

Jenis FSA

1. Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima. Deterministik artinya tertentu/sudah tertentu fungsi transisinya.
Notasi matematis DFA:
• M = nama DFA
• Q = himpunan keadaan DFA
• S = himpunan alfabet
• d = fungsi transisi
• q0 = keadaan awal
• F = keadaan akhir
M = (Q, S, d, q0, F)

2. Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima.
Non-Deterministic Finite Automata:
• Otomata berhingga yang tidak pasti untuk setiap pasangan state input, bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.
• Untuk setiap state tidak selalu tepat ada satu state berikutnya untuk setiap simbol input yang ada.
• Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi)
berlabel simbol input yang sama.
• Untuk NFA harus dicoba semua kemungkinan yang ada sampai
terdapat satu yang mencapai state akhir.
• Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, _, d, S, F) bila {x | d (S,x) memuat sebuah state di dalam F}

Jika disajikan dalam tabel transisi :

* Perhatikan : Dalam cara penulisan state hasil transisi pada tabel transisi untuk NFA, digunakan kurung kurawal ‘{‘ dan ‘}’karena hasil transisisnya merupakan suatu himpunan state.

* Pada bagian ini dapat dilihat NFA dengan lebih dari satu pilihan state berikutnya.

Konfigurasi NFA contoh secara formal adalah sebagai berikut :

Q = {q0, q1,q2,q3,q4 }

d ={0, 1}

S = q0

F = q2

ð =

Contoh :

Pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.
11011 : ditolak
10011 : diterima
11100 : ditolak
10111 : ditolak
11101 : diterima.

II. GRAMMAR DAN BAHASA

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 : • huruf kecil awal 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 : • huruf besar awal 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.
8. Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : α, β, dan γ.
9. Sebuah produksi dilambangkan sebagai α → β, artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol α dengan simbol β.
10. Simbol α dalam produksi berbentuk α → β disebut ruas kiri produksi sedangkan simbol β disebut ruas kanan produksi.
11. Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : α ⇒ β.
12. Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbolsimbol non terminal atau campuran keduanya.
13. Kalimat adalah string yang tersusun atas simbol-simbol terminal. Jelaslah bahwa kalimat adalah kasus khusus dari sentensial.
14. Pengertian terminal berasal dari kata terminate (berakhir), maksudnya derivasi berakhir jika sentensial yang dihasilkan adalah sebuah kalimat (yang tersusun atas simbol-simbol terminal itu).
15. Pengertian non terminal berasal dari kata not terminate (belum/tidak berakhir), maksudnya derivasi belum/tidak berakhir jika sentensial yang dihasilkan mengandung simbol non terminal. 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 ∈ VN : simbol awal (atau simbol start) Q : himpunan produksi

Contoh grammar :