Grammar dan Tingkat Bahasa

CSG3D3 | Teori Komputasi

Grammar dan Tingkat Bahasa

Agung Toto Wibowo Ahmad Suryan Yanti Rusmawati Mahmud Dwi Sulistiyo Kurniawan Nur Ramadhani Said Al Faraby Dede Rohidin

KK Intelligence, Computing, and Multimedia

Pertemuan 2

Manfaat Perkuliahan

Teori Komputasi | CSG3D3

Manfaat Perkuliahan: FA Finite Automata : sangat bermanfaat untuk memodelkan proses pada berbagai hardware dan software FA meliputi DFA dan NDFA Manfaat nyata : – Software untuk mendesain dan mencek perilaku sirkuit digital, contoh: mesin ATM – Bagian “Lexical Analyzer” dari berbagai kompiler yang berfungsi membagi teks input menjadi logical unit seperti keyword, identifier, dan pungtuasi – Search engine  melakukan scanning web dan menemukan kata, frasa, atau pola yang tepat


Manfaat Perkuliahan: Grammar Grammar : model yang sangat bermanfaat untuk mendesain software yang memproses data secara rekursif Grammar meliputi apa yang dibahas atau dikategorikan di hirarki Chomsky Contoh yang paling populer dalam dunia komputer : Parser  bagian kompiler yang mengecek kebenaran atau validitas struktur dari program sumber (source code)


Manfaat Perkuliahan: Regular Expression Ekspresi reguler menyatakan struktur dari sebuah data, khususnya dalam yang berbentuk teks / string

Contoh : Unix Style regular ekspression ‘[A-Z][a-z]*[ ][A-Z] [A-Z]’  merepresentasikan kata berawalan huruf kapital, yang diikuti huruf kecil yang berulang kali, kemudian 1 buah spasi, dan diakhiri dua huruf kapital Materi lainnya adalah Mesin Turing yang merupakan model dari mesin komputer-komputer canggih saat ini


Pertemuan 2

Konsep Bahasa


Konsep Sentral Teori Automata Beberapa istilah penting yang ada di dalam teori automata : – Alphabet : himpunan simbol – String : sequence/list simbol dari alphabet – Language : himpunan string dari alphabet yang sama


Alphabet Alphabet : finite set dan non-empty set dari symbols. Di perkuliahan ini, akan digunakan simbol Σ untuk menyatakan alphabet. Contoh : – Σ = {0, 1}, merupakan alphabet biner – Σ = {a, b, c, .., z}, merupakan alphabet dari lower case – Semua himpunan ASCII adalah alphabet dari karakter ASCII


String [1] String/word : finite sequence symbols yang diambil dari alphabet. Contoh : 01101 merupakan string yang dibangun dari alphabet Σ = {0, 1}. Empty string : string dengan jumlah kemunculan symbol-nya adalah nol. Empty string dinotasikan dengan ε (epsilon) atau λ (lambda). Panjang string : jumlah kemunculan symbol dalam suatu string. Panjang dari string w dinotasikan dengan |w|. Contoh : |10010| = 5 dan |λ| = 0.


String [2] Power of an Alphabet Jika Σ adalah suatu alphabet, maka kita dapat mengekspresikan sekumpulan string dengan panjang tertentu dari alphabet tersebut dengan notasi Σk Contoh : jika Σ = {0, 1}, maka – Σ0 = {λ} – Σ3 = {000, 001, 010, 011, 100,101, 110, 111} – Σ* akan kita sebut sebagai himpunan semua string yang dapat dibangun oleh alphabet – {0, 1}* = {λ, 0, 1, 00, 01, 10, 11, 000, …} – Σ* = Σ0 U Σ1 U Σ 2 U Σ3 U … Teori Komputasi | CSG3D3

Language/Bahasa [1] Language : – Himpunan string yang dipilih dari Σ* dengan aturan tertentu. – Himpunan string dari alphabet yang sama.

Jika Σ adalah alphabet, dan L  Σ* , maka L adalah language yang dapat dihasilkan dari himpunan alphabet Σ. Contoh : – Kata-kata bahasa Indonesia adalah himpunan string dari alphabet 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.


Language/Bahasa [2] Contoh lain : Jika kita punya Σ = {0, 1}, maka definisikan aturan bahasa dari himpunan string berikut! 1. 2. 3.

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


Bahasa sebagai alat komunikasi Aku Cinta Padamu….


Apa yang terjadi ??

Hmmmm… Aku Juga...


Kisah lain …

Gila Lo yah!!!


Poin Diskusi Apa yang diucapkan oleh pembicara?? Bagaimana pendengar dapat memahami maksud pembicara?? Sebenarnya … – Pembicara menggenerate kata-kata (grammer) – Pendengar mengenali kata-kata (recognizer) – Pendengar memahami maksud kata-kata (semantik)


Pertemuan 2

Grammar dan Tingkat Bahasa


Komponen Grammar [1] Suatu grammar / tata bahasa dapat didefinisikan ke dalam bentuk formal : G = (VN, VT, S, F) VN (variabel non terminal) adalah himpunan 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 berupa angka atau simbol lain. – Contoh : ‘a’, ‘b’, ‘c’, ‘1’, ‘0’, ‘+’, ‘-’


Komponen Grammar [2] S (starting symbol) adalah variabel non terminal yang digunakan sebagai awal penurunan produksi. F (aturan produksi) adalah aturan yang menspesifikasikan bagaimana suatu bentuk string/simbol ditransformasikan 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 Teori Komputasi | CSG3D3

Penggolongan Tingkat/Tipe Bahasa [1] Pada tahun 1959, Noam Chomsky menggolongkan bahasa menjadi 4 tingkat (dikenal dengan Hirarki Chomsky) Unrestricted Bahasa Konteks Sensitive Bahasa Bebas Konteks Bahasa Regular


Penggolongan Tingkat/Tipe Bahasa [2]

Bahasa Regular / Tipe 3

Mesin Automata Finite State Automata (FSA) meliputi Deterministic Finite Automata (DFA) dan Non Deterministic Finite Automata (NFA)

Bebas Konteks Push Down Automata / Context Free / (PDA) Tipe 2

Batasan Produksi α adalah sebuah simbol variabel β maksimal memiliki sebuah simbol variabel yang bila ada terletak paling kanan α adalah sebuah simbol variabel


Penggolongan Tingkat/Tipe Bahasa [3]

Bahasa

Mesin Automata

Batasan Produksi

Context Sensitive / Tipe 1

Linier Bounded Automata |α| <= |β|

Unrestricted / Phase Structure / Natural Language / Tipe 0

Mesin Turing

Tidak ada batasan


Penggolongan Tingkat/Tipe Bahasa [4] Bahasa manusia / natural language masuk ke dalam grammar Tipe 0 / Unrestricted, di mana tidak ada batasan pada aturan produksinya. Contoh : Abc  De


Penggolongan Tingkat/Tipe Bahasa [5] Pada bahasa Context Sensitive, terdapat batasan |α| <= |β|. Contoh : Ab  DeF CD  eF Perhatikan S ε – Apakah masuk ke Context Sensitive????

Context Sensitive digunakan untuk proses analisis semantik dalam tahapan kompilasi. Teori Komputasi | CSG3D3

Penggolongan Tingkat/Tipe Bahasa [6] Pada Bebas Konteks (Context Free Grammar), batasan bertambah dengan ruas kiri harus tepat 1 simbol variabel. Contoh : B CDeFg D  BcDe

Bahasa Bebas Konteks menjadi dasar dalam pembentukan suatu parser / analisis sintaksis.


Penggolongan Tingkat/Tipe Bahasa [7] Pada bahasa Reguler, batasan bertambah dengan ruas kanan maksimal memiliki sebuah simbol variabel yang letaknya paling kanan. Contoh : A e | efgC C  cD | D De


Penggolongan Tingkat/Tipe Bahasa [8] Aturan produksi berikut ini tidak legal : ε  Abd karena ruas kiri tidak boleh berupa ε. Aturan berikut juga tidak legal : a  bd ab  bd karena ruas kiri harus memuat simbol yang bisa diturunkan. Aturan-aturan di atas tidak legal untuk aturan produksi tingkat Unrestricted sekalipun. Teori Komputasi | CSG3D3

Studi Kasus dan Diskusi [1] Tentukan jenis grammer dari aturan produksi berikut : 1 : a  bd 2: E  ( E ) | AOE | EOA | A A 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 O*|+|-|: 3: S  xX X  yY Y  xX | λ


Studi Kasus dan Diskusi [2] 4: <sentence>  <subject> <predicate> <subject>  <noun> <noun>  jhon | mary <predicate>  <predicate> 

Grammar dan Tingkat Bahasa

Recommend Documents