grammar dan tingkat bahasa - telkom...

CSG3D3 | Teori Komputasi

Agung Toto Wibowo

Ahmad Suryan

Yanti Rusmawati

Mahmud Dwi Sulistiyo

Kurniawan Nur Ramadhani

Said Al Faraby

Dede Rohidin

KK Intelligence, Computing, and Multimedia

Grammar dan Tingkat Bahasa

Teori Komputasi | CSG3D3

Manfaat Perkuliahan

Pertemuan 2


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


Konsep Bahasa

Pertemuan 2


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 …


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. X = {λ, 01, 0011, 000111, …}

2. Y = {λ, 01, 10, 0011, 0101, 1001, …}

3. 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)


Grammar dan Tingkat Bahasa

Pertemuan 2


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


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



Bahasa Mesin Automata Batasan Produksi

Regular /

Tipe 3

Finite State Automata

(FSA) meliputi

Deterministic Finite

Automata (DFA) dan Non

Deterministic Finite

Automata (NFA)

α adalah sebuah simbol

variabel

β maksimal memiliki

sebuah simbol variabel

yang bila ada terletak

paling kanan

Bebas Konteks

/ Context Free /

Tipe 2

Push Down Automata

(PDA)

α adalah sebuah simbol

variabel



Bahasa Mesin Automata Batasan Produksi

Context

Sensitive

/ Tipe 1

Linier Bounded Automata |α| <= |β|

Unrestricted /

Phase

Structure /

Natural

Language /

Tipe 0

Mesin Turing Tidak ada batasan



Bahasa manusia / natural language masuk ke dalam grammar Tipe 0 / Unrestricted, di mana tidak ada batasan pada aturan produksinya.

Contoh :

Abc De



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.



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.



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



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.


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> <intransitive verb>

<predicate> <transitive verb> <object>

<object> <noun>

<intransitive verb> skates

<transitive verb> likes


Latihan

Pertemuan 2


Latihan 1

Lengkapi tabel berikut.

Nama Bahasa Tipe Syarat

Unrestricted

Context Free

Context Sensitive

Regular


Latihan 2

Manakah dari pernyataan mengenai penggolongan bahasa menurut Chomsky berikut yang benar?

a. Bahasa Reguler lebih luas daripada bahasa Context Free

b. Bahasa Context Sensitive digolongkan ke tipe 2

c. Syarat bahasa dikatakan Unrestricted adalah bagian alpha maksimum 1 variabel non-terminal

d. Jika suatu aturan produksi pada bagian α terdapat 1 variabel non terminal dan bagian β terdapat maksimal 1 variabel non terminal yang letaknya paling kanan, maka bahasa itu adalah Unrestricted.

e. Tidak ada jawaban benar


Latihan 3

Manakah dari aturan produksi berikut yang menyebabkan suatu bahasa menjadi tidak termasuk Context Free?

B B01

B 1B

B 0

0B 1

B B0B


Latihan 4

Diketahui tata bahasa G = ({S}, {a,b}, S, P) dimana P terdiri dari S aaS | Saa | b

aS Sa

Tata bahasa tersebut membangun : a. Bahasa Context Free

b. Bahasa Context Sensitive

c. Bahasa Regular

d. Bahasa Unrestricted

e. Tidak ada yang benar

http://soc.telkomuniversity.ac.id/

grammar dan tingkat bahasa - telkom...

Documents