TEORI BAHASA AUTOMATA BAGIAN 1

Pokok bahasan pada Teori Bahasa Automata (TBA) bagian 1 adalah sebagai berikut :

•  Konsep Bahasa Automata
• Finite State Automata
• Ekivalensi NFA & DFA
• NFA & Ɛ MOVE

I.  Konsep Bahasa Automata

Teori bahasa membicarakan mengenai bahasa formal (formal language) dimana bahasa formal sendiri adalah merupakan suatu abstraksi terdiri dari hipunan simbol-simbol dan aturan-aturan yang mana simbol tersebut bisa dikombinasikan ke dalam entitas yang disebut kalimat. Sebuah bahasa dapat dibangkitan menggunakan tata bahasa tertentu, dalam kasus ini, bahasa formal dapat dibangkitkan dengan dua atau lebih tata bahasa yang berbeda.

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

Berikut adalah beberapa istilah yang dipakai :

-          Simbol adalah entitas abstrak. Huruf dan angka adalah contohnya. Simbol dibagi menjadi 2, yaitu :

Simbol terminal, terdiri dari :

a.       huruf kecil alfabet = a, b, c, ..., z

b.      simbol operator = +, -, dan x

c.       simbol tanda baca = ( , ) dan ( ; )

d.      string yang tercetak tebal = if, then, else

Simbol Non-Terminal, terdiri dari :

a.       huruf besar alfabet = A, B, C, ..., Z

b.      huruf S sebagai simbol awal

c.       string yang tercetak miring = if, then, else

-          String adalah deretan berhingga dari simbol-simbol. Contoh, terdapat 3 buah simbol yaitu : a, b, dan c. Maka, dapat dibangun sebuah string abcb dari ketiga simbol tersebut.

Panjang string dinyatakan dengan | w | dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string. Contoh :

w = abcb maka | w | = 4

String hampa / string kosong adalah string dengan nol simbol. Dinyatakan dengan simbol Ɛ (atau ^) sehingga | Ɛ | = 0

-          Alfabet adalah himpunan berhingga simbol-simbol.

-          Huruf yunani melambangkan string yang tersusun atas simbol terminal atau simbol non-terminal. Misalnya, α, β, γ.

-          Sebuah produksi dilambangkan sebagai α    β dimana derivasi dapat dilakukan dengan penggantian simbol α dengan simbol β. Simbol α disebut ruas kiri produksi, sedangkan simbol β disebut ruas kanan produksi.

-          Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. 

-          Sentensial adalah string yang tersusun atas simbol-simbol terminal dan non-terminal atau campuran keduanya.

Grammar dan Klasifikasi Chomsky

Grammar G didefinisikan sebagai pasangan 4 tuple :

V_T          : Himpunan simbol terminal

V_N          : Himpunan simbol non-terminal

S € V_N   : Simbol awal / Start

Q            : Himpunan produksi

Noam Chomsky, mengklasifikasikan grammar menjadi 4 tipe, yaitu :

Bahasa	Mesin Automata	Batasan Aturan Produksi	Ciri - Ciri
Reguler / tipe 3 / RG	Finite State Automata (FSA) meliputi : 1. DFA (deterministic Finite Automata) 2. NFA (non-deterministic Finite Automata)	α  adalah sebuah simbol variabel β berisi terminal dan variabel (maksimal memiliki sebuah simbol variabel, yang bila ada terletak di posisi paling kanan	α € VN , β € {VT , VT VN } atau α € VN , β € {VT , VN VT }
Bebas Konteks / Context Free / Tipe 2 / CFG	Push Down Automata (PDA)	α berupa sebuah simbol variabel	α, β € (VT | VN )*
Context Sensitive / Tipe 1 / CSG	Linier Bounded Automata	| α |  | β |	α, β € (VT | VN )*, 0 < | α |  | β |
Unrestritcted / Phase Structure / Natural Language / Tipe 0 / UG	Mesin Turing	Tidak ada batasan	α, β € (VT | VN )*, | α | > 0

II. Finite State Automata

Memiliki state-state yang banyaknya berhingga dan dapat berpindah dari satu state ke state yang lain. FSA dapat menerima input dan menghasilkan output.

Contoh :

Lingkaran                    : state

Lingkaran Ganda        : state akhir

Label pada lingkaran   : nama state

Busur                           : transisi / perpindahan

Label pada busur         : simbol input

Secara formal, FSA memiliki 5 tuple :

Q         : Himpunan state

Ʃ          : Himpunan simbol input

δ          : Transisi

S          : State awal

F          : Himpunan state akhir

FSA dibagi menjadi 2, yaitu :

-          DFA (Deterministic Finite Automata), contoh :

Q         : {Q1, Q2, Q3} Ʃ          : {a, b} S          : {Q0} F          : {Q2}

Fungsi Transisi : δ (Q0, a) = Q0 δ (Q0, b) = Q1 δ (Q1, a) = Q1 δ (Q1, b) = Q2 δ (Q2, a) = Q1 δ (Q2, b) = Q2

Tabel Transisi δ a b Q0 Q0 Q1 Q1 Q1 Q2 Q2 Q1 Q2

·     Input akan dapat diterima oleh mesin apabila berakhir pada final state, dalam contoh ini adalah Q2.

·    Sebaliknya, input akan ditolak oleh mesin apabila state berakhir bukan pada final state.

-          NFA (Non-Deterministic Finite Automata), contoh :

Q         : {Q1, Q2} Ʃ          : {a, b} S          : {Q0} F          : {Q2}

Fungsi Transisi : δ (Q0, a) = Q1 δ (Q0, b) = f δ (Q1, a) = Q1 δ (Q1, b) = Q0

Tabel Transisi δ a b Q0 Q1 f Q1 Q1 Q0

Himpunan θ merupakan NFA

·         Jika menerima input kemudian berakhir pada θ, maka input ditolak / direject oleh mesin

·         Jika state satu memiliki 2 tansisi dengan input yang sama merupakan NFA

III. Ekivalensi NFA ke DFA

Dari sebuah mesin NFA dapat dibuat mesin DFA yang ekivalen, yaitu mampu menerima bahasa yang sama. Tahap pengubahan NFA ke DFA adalah :

-          Suatu DFA dapat dipandang sebagai kasus khusus dari NFA

-          Kelas bahasa yang diterima oleh DFA akan diterima oleh DFA

-          DFA juga mensimulasikan NFA : yaitu untuk setiap NFA kita dapat membuat DFA yang ekivalen

-          Dapat dibuktikan bahwa DFA dan NFA adalah ekivalen, sehingga dapat disebut FA

Contoh :

Q         : ({Q1}, {Q2}) Ʃ          : {0, 1} S          : {Q0} F          : {Q1}

Tabel Transisi δ 0 1 Q0 {q0, q1} Q1 Q1 f {q0, q1}

Telusuri setiap state :

-          Q0, 0         = {q0, q1}

-          Qo, 1         = {q1}

-          Q1, 0         = f

-          Q1, 1         = {q0, q1}

-          {q0, q1}, 0 = {q0, q1}

-          {q0, q1}, 1 = {q0, q1}

Maka, hasil penelusurannya dari {q1}, [q0}, {q0, q1}

Q         :  ( qo, { q0, q1 }, q1, f ) Ʃ          : {0, 1} S          : {Q0} F          : ( q1, { q0, q3 })

Tabel Transisi δ 0 1 q0 {q0, q1} q1          f {q0, q1} {q0, q1} {q0, q1} {q0, q1} f f f

             

i            IV. NFA Ɛ-move

Adalah mesin NFA yang diperbolehkan mengubah state tanpa mebaca input. Disebut transisi Ɛ karena tidak bergantung pada suatu input ketika melakukan transisi.

Ekivalensi NFA Ɛ-move ke NFA tanpa Ɛ-move, berikut tahapan-tahapannya :

-          Buat tabel transisi NFA Ɛ-move

-          Tentukan Ɛ-closure untuk tiap state. Ɛ-closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. Suatu state yang tidak memiliki transisi Ɛ maka Ɛ-closurenya adalah state itu sendiri.

-          Cari fungsi hasil perubahan dari NFA Ɛ-move ke NFA tanpa Ɛ-move dengan rumus :

 

δ’ (state, input) = Ɛ-closure (δ (Ɛ-closure(state, input))

-          Buat tabel transisi dan diagram transisi NFA tanpa Ɛ-move yang ekivalensi dengna NFA Ɛ-move Ɛ dari hasil tahap 3

-          Tentukan state akhir untuk NFA tanpa Ɛ-move