CS3113 Teori KomputasiSTT Telkom 2007

Grammer dan Tingkat Bahasa

Agung Toto Wibowoatw@stttelkom.ac.id

Download via http://www.stttelkom.ac.id/staf/atw/

JANGAN JADIKAN SLIDE INI SEBAGAI REFERENSI TUGAS AKHIR / PROYEK AKHIR

Materi dan Manfaatperkuliahan – FA [1]

Finite Automata : model yang sangat bermanfaatuntuk berbagai hardware dan software.FA meliputi DFA dan NFA.Manfaat nyata :

Software untuk mendesain dan mencek perilaku sirkuitdigital. Contoh : mesin ATM.Bagian “Lexical Analyzer” dari berbagai kompiler yang berfungsi membagi teks input menjadi logical unit sepertiKeyword, Identifier, dan pungtuasi.Search engine menscan web, dan menemukan kata, frasa atau pola yang tepat

Materi dan Manfaatperkuliahan – Grammer [2]

Grammer : model yang sangat bermanfaatuntuk mendesain software yang memprosesdata secara rekursif.Grammer meliputi apa yang di bahas / dikategorikan di hirarki ChomskyContoh yang paling populer dalam duniakomputer : Parser bagian kompiler yang mengecek kebenaran / validitas struktur dariprogram sumber.

Materi dan Manfaat perkuliahan– Regular Ekspression [3]

Ekspresi reguler menyatakan struktur daridata khususnya dalam teks / string.Contoh :

Unix Style regular ekspression‘[A-Z][a-z]*[ ][A-Z] [A-Z]’ yang merepresentasikankata berawalan huruf besar, yang diikuti spasidan diakhiri dua huruf kapital.

Materi lainnya adalah Mesin Turing yang merupakan model dari mesin komputer-komputer canggih saat ini.

Konsep SentralTeori Automata

Beberapa istilah penting yang ada di dalamteori automata :

Alphabet – Himpunan simbolString – list simbol dari alphabetLanguage – himpunan string dari alphabet yang sama

Alphabet

Alphabet : finite set dan non-empty set darisimbol. Di perkuliahan kita, akan digunakan Σuntuk menyatakan alphabet.Contoh : Σ = {0, 1}, merupakan alphabet binerΣ = {a, b, c, .., z}, merupakan alphabet dari lower caseSemua himpunan ASCII adalah alphabet darikarakter ASCII

String [1]String / word : finite sequence symbols yang diambil dari alphabet. Contoh : 01101 merupakanstring dari alphabet Σ = {0, 1}.Empty string : string dengan kemunculan symbol adalah nol. Empty string dinotasikan dengan ε(dibuku 3) atau λ (dibuku 1 – yang kita gunakan).Panjang String : panjang dari string w dinotasikandengan |w| adalah jumlah kemunculan symbol dalam suatu string. Contoh : |10010| = 5 dan |λ| = 0.

String [2]Power of an Alphabet

Jika Σ adalah suatu alphabet, maka kita dapatmengekspresikan sekumpulan string denganpanjang tertentu dari alphabet dengan cara Σk

Contoh : jika Σ = {0, 1}, makaΣ0 = {λ}Σ3 = {000, 001, 010, 011, 100,101, 110, 111}Σ* akan kita sebut sebagai himpunan string yang dapatdibangun oleh alphabet{0, 1}* = {λ, 0, 1, 00, 01, 10, 11, 000, …}Σ* = Σ0 U Σ1 U Σ2 U Σ3 U …

Laguage / Bahasa [1]Language : himpunan string yang dipilih dari Σ* .Jika Σ adalah alphabet, dan L ⊆ Σ* , maka L adalahlanguage yang bisa di hasilkan oleh himpunanalphabet Σ.Contoh :

Kata-kata bahasa Indonesia adalah himpunan string darialphabet yang semuanya terdiri atas huruf.Di bahasa C atau pemrograman lain, program yang legal adalah subset dari semua kemungkinan string yang dibangun dari alphabet di bahasa pemrograman itu.

Laguage / Bahasa [2]

Contoh lain : jika kita punya Σ = {0, 1}, makadefinisikan bahasa dari himpunan string berikut :

X = {λ, 01, 0011, 000111, …}Y = {λ, 01, 10, 0011, 0101, 1001, …}Z = {10, 11, 101, 111, 1011, …}

Bahasa sebagaiAlat Komunikasi

Apa yang terjadi???

Kisah Lain

Point Diskusi

Apa yang diucapkan oleh Pembicara???Bagaimana Pendengar dapat memahamimaksud pembicara?Sebenarnya….

Pembicara menggenerate kata-kata (grammer)Pendengar mengenali kata-kata (recognizer)Pendengar memahami maksud kata-kata(semantik)

Komponen Grammer [1]Suatu Grammer / tata bahasa dapat didefinikan kedalam bentuk formal :

G = (VN, VT, S, F)Di mana VN (variabel non terminal) adalahhimpunan simbol yang masih bisa diturunkan.

VN biasanya dituliskan dalam huruf kapital.Contoh ‘A’, ‘B’, ‘C’, ‘S’

VT (variabel terminal) adalah himpunan simbol yang sudah tidak bisa diturunkan lagi.

VT biasanya dituliskan dalam hurul kecil, dan bisa berupaangka atau simbol lain.Contoh ‘a’, ‘b’, ‘c’, ‘1’, ‘0’, ‘+’, ‘-’

Komponen Grammer [2]S (starting symbol) adalah variabel non terminal yang digunakan sebagai awal penurunan produksi.F (aturan produksi) adalah aturan yang menspesifikasikan bagaimana mentransformasisuatu string ke bentuk lainnya.

Kita akan menuliskan aturan produksi dalam bentuk α β.Contoh :

T a (dibaca T menghasilkan a)E T | T+E

α minimal mengandung 1 variabel nonterminal

Penggolongan Tingkat / TipeBahasa [1]

Pada tahun 1959, Noam Chomsky menggolongkan bahasamenjadi 4 tingkatan (dikenal dengan Hirarki Chomsky)

Penggolongan Tingkat / TipeBahasa [2]

Bahasa Mesin Automata Batasan ProduksiRegular / Tipe 3

Finite State Automata (FSA) meliputiDeterministic Finite Automata (DFA) dan Non Deterministic Finite Automata (NFA)

α adalah sebuah simbolvariabelβ maksimal memilikisebuah simbol variabelyang bila ada terletakpaling kanan

Bebas Konteks/ Context Free /Tipe 2

Push Down Automata (PDA)

α adalah sebuah simbolvariabel

Penggolongan Tingkat / TipeBahasa [3]

Bahasa Mesin Automata Batasan ProduksiContext Sensitive/ Tipe 1

Linier Bounded Automata |α| <= |β|

Unrestricted / Phase Structure / Natural Language / Tipe 0

Mesin Turing Tidak ada batasan

Penggolongan Tingkat / TipeBahasa [4]

Bahasa manusia / natural language masukke dalam grammer Tipe 0 / Unrestricted, dimana tidak ada batasan pada aturanproduksinya.

Contoh : Abc De

Penggolongan Tingkat / TipeBahasa [5]

Pada bahasa Context Sensitive, |α| <= |β|.Contoh :

Ab DeFCD eF

Perhatikan S ε. Apakah masuk ke Context Sensitive????

Context Sensitive digunakan untuk prosesanalisis semantik dalam tahapan kompilasi.

Penggolongan Tingkat / TipeBahasa [6]

Pada bebas konteks, (context free grammer) batasan bertambah dengan ruas kiri harustepat 1 simbol variabel.

Contoh :B CDeFgD BcDe

Bahasa bebas konteks menjadi dasar dalampembentukan suatu parser / analisis sintaksis.

Penggolongan Tingkat / TipeBahasa [7]

Pada bahasa reguler, batasan ini bertambahdengan ruas kanan maksimal memilikisebuah simbol variabel yang letaknya paling kanan.

Contoh :A e | efgCC cD | DD e

Penggolongan Tingkat / TipeBahasa [8]

Aturan produksi beriku ini tidak legal :ε Abd

karena ruas kiri tidak boleh berupa ε.Aturan berikut juga tidak legal :

a bdab bd

karena ruas kiri harus memuat simbol yang bisaditurunkan. Aturan di atas tidak legal untuk aturan produksiyang Unrestricted sekalipun.

Studi Kasus dan Diskusi [1]Tentukan jenis grammer dari aturan produksi berikut:1. : a bd

2. :E ( E ) | AOE | EOA | AA 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9O * | + | - | :

3 :S xXX yYY xX | λ

Studi Kasus dan Diskusi [2]

4. <sentence> <subject> <predicate><subject> <noun><noun> jhon | mary<predicate> <intransitive verb><predicate> <transitive verb> <object><object> <noun><intransitive verb> skates<transitive verb> likes

Tugas :

Baca materi Buku 1 chapter 1.1 s/d 1.5

Daftar Pustaka1. Brookshear, Glen. J. “Theory of Computation :

Formal Language, Automata and Complexity”, The Benjamin/Cummings Publishing Company, 1989

2. Hopcroft, Jhon E. and Jeffery D. Ullman, “Introduction to Automata Theory, Language, and Computation”

3. Utdirartatmo, Firrar “Teknik Kompilasi”, J&J Learning Yogyakarta, 2001 ISBN:979-9398-11-8