PRAKTIKUM

TEORI BAHASA DAN OTOMATA

Laporan ini dibuat untuk memenuhi salah satu tugas praktikum Teori Bahasa dan Otomata

Dosen : Nurdyanto M.T

Disusun Oleh :

Asep Hendar Rustiawan

(0706014)

JURUSAN TEKNIK INFORMATIKA

SEKOLAH TINGGI TEKNOLOG GARUT

2009

MODUL I

FINITE STATE AUTOMATA FSA)

A. Landasan Teori

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 Natural/manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan

kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan

disebut ‘bahasa’ saja.

Hierarki Bahasa

Kelas Mesin Pengenl

Regular Language

Context Free Language

Context Sensitive Language

Unrestricted language

Finite State Automta

Push Down Automata

Linear Bounded Automata

Turing Machine

Teori Otomata adalah teori mengenai mesin-mesin abstrak dan masalah yang dapat

dipecahkannya, dan berkaitan erat dengan teori bahasa formal. Otomata sendiri adalah suatu

bentuk yang memiliki fungsi-fungsi dari komputer digital Menerima input, menghasilkan output,

bisa memiliki penyimpanan sementara, dan mampu membuat keputusan dalam

mentransformasikan input ke output. Sebuah bahasa formal adalah abstraksi terdiri dari

himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa

dikombinasikan kedalam entitas yang disebut kalimat.

Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state

menyatakan informasi mengenai input yang lalu,dan dapat pula dianggap sebagai memori mesin.

Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya

mesin otomata membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak. 

Automaton adalah model matematika dari sebuah Finite State Machine (FSM). FSM adalah

sebuah mesin yang apabila diberikan masukan berupa simbol, kemudian akan melompat melalui

rangkaian status berdasarkan fungsi transisi. Setiap simbol dibaca satu per satu sampai seluruh

simbol yang harus diinterpretasi habis. Mesin Otomata Sederhana Sebuah string input diterima

bila mencapai state akhir/final state yang digambarkan dengan lingkaran ganda.

Finite State Automata

♦ 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

♦ Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.

♦ Mekanisme kerja dapat diaplikasikan pada : elevator, text editor, analisa leksikal,

pencek parity.

Diagram transisi FSA dapat digambarkan sebagai berikut:

Keterangan: q0 = state awal

q1 = state akhir

= transsisi

FSA dibangun dengan 5 Tupel :

Q = himpunan state

= himpunan simbol input

= himpunan transisi

S = state awal

F = himpunan state akhir

B. Jawaban Hasil Praktek

MODUL II

PUSHDOWN AUTOMATA (PDA)

A. Landasan Teori

PDA adalah mesin otomata yang memiliki kendali masukan menggunakan teknik LIFO (Last

IN First Out),untuk menentukan apakah suatu output diterima atau tidak oleh mesin

tersebut.Dalam melakukan proses peneriman input,PDA menggunakn memory stack.

Mekanisme kerja memory stackadalh menyimpan input pertama pada alamat paling bawah,input

berikutnya disimpan pada alamat diatasnya,dan input terakhir disimpan pada alamat paling

atas.petrintah opersi yang dgunakan untuk menyimpan input pada stack adalah

“PUSH”.Sedangkan perintah operasi untuk mengeluarkan input yang telah tersimpan adalah

“POP”.

Sebuah PDA dinyatakan dengan 7 tupel :

Q = himpunan state

= himpunan symbol input

T = simbol stack

= fungsi transisi

S = state awal

F = state akhir

Z = top of stack

Diagram transisi PDA dapat digambarkan sebagai berikut:

Keterangan: q0 = state awal

q3 = state akhir

= transsisi

B. Jawaban Hasil Praktek

MODUL III

MESIN TURING

A. Landasan Teori

Stack tumpukan yang terdapat pada PDA memiliki keterbatasan kemampuan akses,yaitu hanya

mengakses data yang terdapat pada top/puncak dari stack.untuk melakukan akses pada bagian

yang lebih rendah dari puncak stack, harus memindahkan bagian diatasnya (POP), yang mana

akan menyebabkan bagan tersebut hilang.

Pada Mesin Turing, memori berupa suatu pita yang pada dasarnya berupa array (deretan) sel-sel

penyimpanan. Setiap sel mampu menyimpan sebuah symbol tunggal. Pita tersebut tidak

mempunyai sel pertama dan sel terakhir. Pita dapat memuat informasi dalam jumlah tak terbatas,

dan dapat diakses bagian manapun dari pita dengan urutan bagaimanapun. Terdapat seuah head

yang menunjukan posisi yang diakses pada pita. Head dapat bergerak kekanan dan kekiri untuk

membaca input dari pita dan sekaligus juga bisa melakukan penulisn pada pita/mengubah isi pita.

Mesin Turing bisa dianalogikan seperti computer sederhan, dengan sejumlah state sebagai

memori, Pita sebagai secondry storage, fungsi transisi sebagai program.Sebuah Mesin Turing

secara formal dinyatakan dalam 7 tupel, yaitu M = {Q, , , , S, F, b).

Dimana:

Q = himpunan state

= himpunan simbol input

= simbol pada pita

= fungsi trnsisi

S = state awal, S Q

F = himpunan state akhir

b = simbol kosong

Bagian dari pita yng belum ditulisi dianggap berisi simbo b (blank).

B. Jawaban Hasil Praktek