TEORI BAHASA DAN OTOMATA

Quido Kainde,ST.,MM.,MT2012

Tatap Muka 20% (4 kali tidak hadir)

Mandiri/quiz 20%

UTS 30%

AS 30%

● PENILAIAN

Pengantar•Otomata bermula sebelum komputer ada pada teori di bidang sistemlogika matematika atau formal

•Pengembangan teori otomata, komputasi dan teori bahasa difasilitasi perkembangan bidang psyco-linguistic

- Apakah bahasa secara umum?

- Bagaimana manusia mengembangkan bahasa?

- Bagaimana manusia memahami bahasa?

- Bagaimana manusia mengajarkan bahasa ke anak-anaknya?

- Apa gagasan-gagasan yang dapat dinyatakan dan bagaimana caranya?

- Bagaimana manusia membangun kalimat-kalimat dari gagasan-gagasan yang berada di pikirannya?

•Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa komputer

- Grammar berisi sejumlah aturan serta menspesifikasikan bahasa tertentu.

- Bahasa berisi semua string yang dapat dihasilkan menggunakan aturan2 grammar

•Terdapat 3 model komputasi pada teori otomata.- Finite automata

- Pushdown automata

- Turing Machine

•Beberapa bidang ilmu lain yang mendukung pengembangan metode komputasi :

- Biologi

Mempelajari jaringan neuron yang mengilhami ditemukanannya finite automata.

- Rangkaian Elektronika

Mempelajari teori switching sebagai perancangan perangkat keras menggunakan finite automata

- Matematika

Mengembangkan system logika yang berguna untuk masalah pembuktian automata.

Teori Bahasa•Teori bahasa membicarakan bahasaformal (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

•Bahasa adalah beberapa variabel yang dapat dibentuk dari himpunan alfabet, atau rangkaian simbol-simbol yang mempunyai makna

OTOMATA•Arti menurut American Heritage Dictionary:

1. a robot

2. one that behaves in an automatic or mechanical fashion

•Arti dalam dunia matematika

Berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input, dan mengeluarkan output, dalam bentuk diskrit

Contoh :

–Mesin Jaja / vending machine

mesin yang dpt mengeluarkan sesuatu

•Mesin penukar uang

•Model transmisi data

•Kunci kombinasi

•Parser/compiler

•Adalah suatu sistem yang terdiri atas sejumlah berhingga state yang mempelajari tentang mesin abstrak yang menerima input dan mengeluarkan output dalam bentuk diskret (satu per satu)

•State adalah suatu kondisi yang menyatakan informasi mengenai input yang lalu.

State dianggap sebagai memori mesin.

•Input pada otomata dianggap sebagai batas yang harus dikenali oleh mesin

•Pembangkitan kalimat/generation : menghasilkan semuakalimat dalam bahasa L berdasarkan aturan yang dimilikinya

•Pengenalan kalimat / recognition: menentukan suatu string (kalimat) termasuk sebagai salah satu anggota himpunan L

•Simbol adalah sebuah entitas abstrak. 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 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

•Alfabet adalah hinpunan hingga (finite set) simbol-simbol

Diberikan dua string : x= abc, dan y= 123

•Prefik string wadalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.

Contoh : abc, ab, a, dan Ɛ adalah semua Prefix(x)

•ProperPrefix string w adalah string yang dihasilkan dari string wdengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string wtersebut.

Contoh : ab, a, dan Ɛ adalah semua ProperPrefix(x)

•Postfix (atau Sufix) string wadalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.

Contoh : abc, bc, c, dan Ɛ adalah semua Postfix(x)

•ProperPostfix (atau PoperSufix) string wadalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut.

Contoh : bc, c, dan Ɛ adalah semua ProperPostfix(x)

•Head string w adalah simbol paling depan dari string w.

Contoh : a adalah Head(x)

•Tail string w adalah string yang dihasilkan dari string wdengan menghilangkan simbol paling depan dari string w tersebut.

Contoh : bc adalah Tail(x)

•Substring string wadalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.

•Contoh : abc, ab, bc, a, b,c, dan Ɛ adalah semua Substring(x)

•ProperSubstring string wadalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.

Contoh : ab, bc, a, b,c, dan Ɛ adalah semua Substring(x)

•Subsequence string wadalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol dari string w tersebut.

Contoh : abc,ab, bc, ac, a, b,c, dan Ɛ adalah semua Subsequence(x)

•ProperSubsequence string wadalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol dari string w tersebut.

Contoh : ab, bc, ac, a, b,c, dan Ɛ adalah semuaSubsequence(x)

•Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun

Contoh : concate(xy) = xy = abc123

•Alternation adalah pilihan satu di antara dua buah string. Operator alternation adalah alternate atau |

Contoh : alternate(xy) = x | y = abc atau123

- Kleene Closure : x* = Ɛ|x|xx|xxx|… = Ɛ|x|x|x|…

- Positive Closure : x= x|xx|xxx|… = x|x|x|…