TEORI BAHASA DAN OTOMATA1. PENDAHULUAN Teori Bahasa Teori bahasa membicarakan tentang bahasa formal (formal language), terutama untuk perancangan kompilator (compiler) dan pemroses naskah (text processor).

Bahasa formal adalah kumpulan kalimat.

Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa

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

2. KONSEP DASAR String adalah deretan terbatas (finite) symbol-simbol.

String hampa adalah string dengan nol buah simbol

Dalam grammmar, dikenal symbol-symbol, yaitu :

1. Simbol terminal (token)Adalah symbol-simbol yang dilambangkan dengan huruf kecil, dan symbol-simbol tersebut sudah tidak dapat diturunkan lagiContoh : a, b, c

2. Simbol non terminal(variable)Adalah symbol-simbol yang dilambangkan dengan huruf besar, dan symbol-simbol tersebut masih dapat diturunkan lagiContoh : A, B, C

3. Simbol Awal (Start)Adalah symbol awal, biasanya dilambangkan dengan S

Aturan produksi dilambangkan dengan :

: artinya dapat diganti atau diturunkan dengan symbol Derivasi kalimat (pembentukan kalimat) dilambangkan dengan :

: artinya adalah kalimat yang terdiri dari deretan symbol 3. GRAMMAR DAN KLASIFIKASI CHOMSCYGrammar (G) didefinisikan sebagai pasangan 4 tuple yaitu : VT : himpunan symbol terminal

VN : himpunan symbol non terminalS : symbol awal (start)

Q : himpunan produksi

Teori Bahasa Automata ~ Lina Susanti, S. KomDerivasi kalimat dan penentuan bahasa :Contoh :

Tentukan bahasa dari masing-masing grammar dari aturan produksi berikut :

1. G dengan Q = {1. SaAa, 2. A Aa, 3. Ab } Penyelesaian :

a. Derivasi kalimat terpendek (hindari aturan produksi yang menyebabkan looping):

S aAa (1)

aba (3)

b. Derivasi kalimat terpendek 1 (semua aturan produksi terlibat, tetapi tidak ada looping):

c. Derivasi kalimat umum (semua aturan produksi terlibat dan ada looping):S aAa(1)

aAaa(2)

aAaaa(2)

aAaaaa(2)

.

aAan(2)

aban(3)

Dari pola kedua buah kalimat dapat disimpulkan L(G) = {aban n1}2. G dengan Q = {1. SAb, 2. A Bc, 3. BCb, 4. CCa, 5. Ca} Penyelesaian :

a. Derivasi kalimat terpendek :S Ab(1)

Bcb(2)

Cbcb(3)

abcb(5)

b. Derivasi kalimat terpendek 1: S Ab (1)

Bcb (2)

Cbcb (3)

Cabcb (4)

aabcb (5)

c. Derivasi umum :

S Ab (1)

Bcb (2)

Cbcb (3)

Cabcb (4)

Caabcb (4)

Caaabcb (4)

.

aaaabcb (5)

Dari pola kedua buah kalimat dapat disimpulkan L(G) = {an bcb n1}Teori Bahasa Automata ~ Lina Susanti, S. Kom3. G dengan Q = {1. SA, 2. AaB, 3. BC, 4. CbD, 5. DA,

6. DE, 7. EF, 8. FbG }Penyelesaian :

a. Derivasi kalimat terpendek :S A(1)

aB(2)

aC(3)

abD(4)

abE(6)

abF(7)

abbG(8)

b. Derivasi kalimat umum :

S A (1)

aB (2)

aC (3)

abD (4)

abA (5)..looping pertama

abaB (2)

abaC (3)

ababD (4)

ababA (5).looping ke-2

ababaB (2)

ababaC (3)

abababD (4)

abababE (6)

abababF (7)

abababbG (8)

Dari pola kedua buah kalimat dapat disimpulkan L(G) = {(ab)n bGn1}Latihan soal :Dari aturan produksi dibawah ini cari derivasi kalimat terpendek dan derivasi kalimat umum untuk menentukan grammar dari masing-masing kalimat :

1. G dengan Q = {1. SBA, 2. A aBa, 3. Bb }

2. G dengan Q = {1. SaS, 2. S aB, 3. BbC, 4. CaC, 5. Ca}

3. G dengan Q = {1. SaSBC, 2. SabB, 3. bBbb, 4. bCbc, 5. CBBC,

6. cCcc}Teori Bahasa Automata ~ Lina Susanti, S. KomFINITE STATE AUTOMATA (FSA)Merupakan model matematika yang dapat menerima input dan mengeluarkan output Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi

Tuple pada FSA :

Q = himpunan state

= himpunan symbol input

= fungsi transisi

S = state awal

F = state akhir (dilambangkan dengan lingkaran ganda)Contoh 1 :

q0 a q1 b q2 a q3bcq4q5Q = {q0, q1,q2,q3,q4,q5}

= {a,b,c} S = q0

F = {q3, q4}abc

q0q1

q1q2

q2q3q4q5

q3

q4

q5

Dari gambar mesin automata diatas :

Input yang dapat diterima adalah : aba, abb (karena berakhir pada state akhir) Input yang ditolak adalah : abc (tidak berakhir pada state akhir)

Contoh 2:Q = {genap, ganjil}

= {0,1} S = genap F = ganjil

Teori Bahasa Automata ~ Lina Susanti, S. Kom01

Genapgenapganjil

Ganjilganjilgenap

Atau :

(genap,0) = genap (genap,1) = ganjil (ganjil,0) = ganjil (ganjil,1) = genap

dari mesin automata tersebut:

input yang diterima adalah : 1, 010, 10

input yang ditolak adalah : 11, 011, 101, 0101, 011

Jenis FSA :

1. Deterministic State Automata (DFA)

2. Non Determinictic State Automata (NFA)

Teori Bahasa Automata ~ Lina Susanti, S. KomDETERMINISTIC STATE AUTOMATA (DFA)Dari suatu state ada tepat satu state berikutnya untuk setiap symbol masukan yang diterima.

Contoh 1:Q = {q0, q1,q2 }

= {a,b} S = q0

F = q2ab

q0q0q1

q1q1q2

q2q1q2

(q0,a) = q0

(q0,b) = q1 (q1,a) = q1 (q1,b) =q2 (q2,a) = q1 (q2,b) = q2

contoh 2 :

Q = {q0, q1,q2,q3 }

= {0,1} S = q0

F = q001

q0q2q1

q1q3q0

q2q0q3

q3q1q2

Teori Bahasa Automata ~ Lina Susanti, S. Kom(q0,0) = q2 (q0,1) = q1 (q1,0) = q3 (q1,1) =q0 (q2,0) = q0 (q2,1) = q3 (q3,0) = q1 (q3,1) = q2

Latihan soal1. Gambarkan mesin automata berdasarkan digram fungsi transisi berikut : Q = {q0, q1,q2,q3, q4 }

= {a,b} S = q0

F = {q0, q1, q2} Fungsi transisi DFA :

2. Berdasarkan mesin automata berikut gambarkan diagram fungsi transisinya3. Berdasarkan mesin automata berikut gambarkan diagram fungsi transisinyaTeori Bahasa Automata ~ Lina Susanti, S. KomS aAa(1)aAaa(2)aba(3)

01q0q0q1q1q0q2q2q0q3q3q3q4