Pemodelan Komputasi

Sekolah Tinggi Sandi Negara

1

Pemodelan Komputasi

• Diberikan sebuah tugas:• Dapatkah tugas tersebut diselesaikan dengan menggunakan

komputer?• Kita dapat mempelajari terlebih dahulu beberapa tugas yang

tidak dapat diselesaikan?• Untuk tugas yang dapat diselesaikan dengan menggunakan

komputer, bagaimana tugas tersebut dapat diselesaikan?1. Mempelajari terlebih dahulu konsep sebuah algoritma.

– Deskripsi prosedur perhitungan.2. Bagaimana memodelkan sendiri, dan apa yang dilakukan pada

saat menyelesaikan algoritma tersebut?

• Pemodelan Komputasi – • memodelkan proses abstrak dari perhitungan sendiri.

• Tiga tipe struktur yang digunakan dalam pemodelan komputasi:

• Grammars• Digunakan untuk men-generate kalimat dari bahasa (language) dan

menentukan jika diberikan kalimat dalam suatu bahasa.• Formal languages, di-generate oleh grammars, menyediakan model untuk

bahasa pemogramana (Java, C, Delphi, etc) penting untuk membuat compilers

• Finite-state machines (FSM)• FSM dikarakteristikkan dengan sebuah himpunan states, input alphabet,

dan fungsi transisi yang menentukan state selanjutnya dari pasangan state dengan input.

• FSM dengan dan tanpa output. Mereka digunakan dalam language recognition (sama dengan grammar) tetapi juga untuk tugas lain, seperti vending machines

• Turing Machine – • Merupakan abstraksi komputer; digunakan untuk menghitung fungsi

teoritis. 3

Models Perhitungan

• Teori Fungsi Rekursif – Kleene, Church, Turing, Post, 1930’s (sebelum computers!!)

• Turing Machines – Turing, 1940’s (didefiniskan: computable) • RAM Machines – von Neumann, 1940’s (“real computer”)• Cellular Automata – von Neumann, 1950’s • (Wolfram 2005; physics of our world?)• Finite-state machines, pushdown automata – various people,

1950’s• VLSI models – 1970s (integrated circuits made of thousands of transistors form a single chip)

• Parallel RAMs, etc. – 1980’s

Komputer sebagai Fungsi Transisi

• Sebuah komputer dapat dimodelkan pada setiap saat dengan state khusus sS dari state space S .

• Komputer dapat menerima input symbol iI dan menghasilkan output symbol oO, dimana I dan O adalah himpunan simbols.• Tiap “symbol” dapat mengkodekan sejumlah data

yang berubah-ubah.

• Komputer dapat dimodelkan sebagai penyerdehanaan dari transition function T:S×I → S×O.– Diberikan state lama dan input, fungsinya akan

dipetakan ke state baru beserta outputnya.

Language Recognition Problem

• Misal sembarang himpunan language L dari objek s yang akan dibentuk “kalimat (sentences).”– Kalimat dari language “legal” atau “benar secara grammar”.

• language recognition problem untuk L:– Diberikan sebuah kalimat s, apakah legal sentence dari

language L? • Apakah sL?

1.Languages and Grammars2.Finite-State Machines with Output3.Finite-State Machines with No Output4.Language Recognition 5.Turing Machines

Modeling Computations

Languages & Grammars• Phrase-Structure Grammars• Types of Phrase-Structure Grammars• Derivation Trees• Backus-Naur Form

Pendahuluan Languages• Grammar bahasa Inggris jika diberikan kombinasi kata-kata

merupakan kalimat valid. • Sintaks kalimat menitikberatkan pada bentuknya sementara semantik

menitikberatkan artinya.contoh: the cat wrote a poem

• Dari sintaks menggambarkan kalimat valid.

• Dari semantik tidak menggambarkan secara cepat dengan benar...bisa digambarkan kemungkinannya diambil dari Disney land

• Natural languages (English, French, dll) mempunyai aturan sintaks yang sangat kompleks dan tidak perlu didefinisikan dengan baik.

9

Formal Language

• Formal language – dispesifikasikan dengan aturans sintaks yang berlaku.

• Dua pertanyaan formal language menggunakan grammar.1. Apakah kombinasi kata-kata valid sentence dalam formal

language?2. Bagaimana kita dapat mengenerate valid sentences dari

formal language?

• Formal languages menyediakan model untuk natural languages dan programming languages.

10

Grammars• Sebuah formal grammar G merupakan definisi

matematika dari language L.– As opposed to just a raw listing of all of the language’s

legal sentences, or just examples of them.• Sebuah grammar dapat diartikan sebagai algoritma

yang akan mengenerate semua legal sentences dari language.– Seringkali dibutuhkan definisi rekursif.

• Sebuah cara yang terkenal untuk menentukan grammar secara rekursif adalah menentukan sebagai phrase-structure grammar.

Grammars (Semi-formal)

Contoh: grammar yang mengenerate subhimpunan dari English language

12verbpredicate

nounarticlephrasenoun

predicatephrasenounsentence

_

_

13

sleepsverb

runsverb

dognoun

boynoun

thearticle

aarticle

• A derivation of “the boy sleeps”:

14

sleepsboythe

verbboythe

verbnounthe

verbnounarticle

verbphrasenoun

predicatephrasenounsentence

_

_

• Pembentukan kalimat dari “a dog runs”

15runsdogaverbdoga

verbnounaverbnounarticleverbphrasenounpredicatephrasenounsentence

__

Language of the grammar:

16

L = { “a boy runs”, “a boy sleeps”, “the boy runs”, “the boy sleeps”, “a dog runs”, “a dog sleeps”, “the dog runs”, “the dog sleeps” }

Notasi

17

dognounboynoun

Variabel atauNonterminal

Simbol dari vocabulary

Simbol Terminaldari vocabulary

Aturan

Basic Terminology

► vocabulary/alphabet, V adalah himpuan tak kosong hingga dari elemen yang disebut simbol.

• Contoh: V = {a, b, c, A, B, C, S}

► word/sentence atas V adalah string dengan panjang hingga dari element V.

• Contoh: Aba

► empty/null string, λ adalah string tanpa simbol.

► V* adalah himpunan semua kata-kata atas V.• Contoh: V* = {Aba, BBa, bAA, cab …}

► language atas V adalah subset dari V*.

Phrase-Structure GrammarsG = (V,T,S,P) terdiri dari 4-tuple, yaitu:– V adalah himpunan simbol dari vocabulary– T V adalah himpunan simbol yang disebut terminals • N :≡ V − T adalah himpunan “simbol” khusus yang

disebut nonterminals. – SN adalah nonterminal khusus (start symbol).• Didalam contoh start symbol adalah semacam

“sentence”.– P adalah himpunan productions yang didefinisikan dengan

aturan untuk mensubstitusi satu bagian kalimat untuk kalimat lainnya.• Setiap aturan production pasti memuat paling sedikit

satu nonterminal di bagian sisi kirinya.

Phrase-structure Grammar

Contoh:

Misal diketahui G = (V, T, S, P), dimana V = {a, b, A, B, S}

T = {a, b}, S : start symbol P = {S → ABa, A → BB, B → ab, A → Bb}.

G adalah Phrase-Structure Grammar.

Kalimat apa yang dapat dibentuk dengan grammar ini?

DerivationDefinition•Misal G=(V,T,S,P) phrase-structure grammar.•Misal w0=lz0r (rangkaian dari l, z0, dan r) w1=lz1r strings atas V.

•Jika z0 z1 production dari G, maka we say that w1 is directly derivable from w0 and we write wo => w1.

•If w0, w1, …., wn are strings over V such that w0 =>w1,w1=>w2,…, wn-

1 => wn, then we say that wn is derivable from w0, and write w0=>*wn.

•The sequence of steps used to obtain wn from wo is called a derivation.

Language

• Let G(V,T,S,P) be a phrase-structure grammar. The • language generated by G (or the language of G) • denoted by L(G) , is the set of all strings of terminals • that are derivable from the starting state S.

• L(G)= {w T* | S =>*w}

24

Language L(G)

► EXAMPLE:• Let G = (V, T, S, P), where V = {a, b, A, S}, T = {a, b}, S is a start

symbol and P = {S → aA, S → b, A → aa}.

• The language of this grammar is given by L (G) = {b, aaa};

• we can derive aA from using S → aA, and then derive aaa using A → aa.

• We can also derive b using S → b.

Another example

• Grammar:

• Derivation of sentence :

26

SaSbS

abaSbS

ab

aSbS S

G=(V,T,S,P) P = T={a,b}

V={a,b,S}

• Grammar:

• Derivation of sentence :

27

aabbaaSbbaSbS

aSbS S

aabb

SaSbS

• Other derivations:

28

aaabbbaaaSbbbaaSbbaSbS

aaaabbbbaaaaSbbbbaaaSbbbaaSbbaSbS

So, what’s the language of the grammar with the productions?

SaSbS

• Language of the grammar with the productions:

29

SaSbS

}0:{ nbaL nn

PSG Example – English Fragment

• We have G = (V, T, S, P), where:• V = {(sentence), (noun phrase),

(verb phrase), (article), (adjective), (noun), (verb), (adverb), a, the, large,

hungry, rabbit, mathematician, eats, hops, quickly, wildly}

• T = {a, the, large, hungry, rabbit, mathematician, eats, hops, quickly, wildly}

• S = (sentence)• P = (see next slide)

Productions for our Language

• P = { (sentence) → (noun phrase) (verb phrase),(noun phrase) → (article) (adjective) (noun),(noun phrase) → (article) (noun),(verb phrase) → (verb) (adverb),(verb phrase) → (verb), (article) → a, (article) → the,(adjective) → large, (adjective) → hungry,(noun) → rabbit, (noun) → mathematician,(verb) → eats, (verb) → hops,(adverb) → quickly, (adverb) → wildly }

A Sample Sentence Derivation

• (sentence) (noun phrase) (verb phrase)

• (article) (adj.) (noun) (verb phrase)• (art.) (adj.) (noun) (verb) (adverb)• the (adj.) (noun) (verb) (adverb)

the large (noun) (verb) (adverb) the large rabbit (verb) (adverb)

• the large rabbit hops (adverb) • the large rabbit hops quickly

On each step,we apply a production to a fragment of the previous sentence template to get a new sentence template. Finally, we end up with a sequence of terminals (real words), that is, a sentence of our language L.

Another Example

• Let G = ({a, b, A, B, S}, {a, b}, S,

• {S → ABa, A → BB, B → ab, AB → b}).• One possible derivation in this grammar is:

S ABa Aaba BBaba Bababa abababa.

V T

P

Defining the PSG Types• Type 0: Phase-structure grammars – no restrictions on the

production rules• Type 1: Context-Sensitive PSG:– All after fragments are either longer than the corresponding before

fragments, or empty: if b → a, then |b| < |a| a = λ .

• Type 2: Context-Free PSG:– All before fragments have length 1 and are nonterminals:

if b → a, then |b| = 1 (b N).• Type 3: Regular PSGs:– All before fragments have length 1 and nonterminals– All after fragments are either single terminals, or a pair of a terminal

followed by a nonterminal. if b → a, then a T a TN.

Types of Grammars - Chomsky hierarchy of languages

• Venn Diagram of Grammar Types:

Type 0 – Phrase-structure GrammarsType 1 –

Context-SensitiveType 2 –

Context-Free

Type 3 –Regular

Classifying grammars

• Given a grammar, we need to be able to find the smallest class in which it belongs. This can be determined by answering three questions:

• Are the left hand sides of all of the productions single non-terminals?

• If yes, does each of the productions create at most one non-terminal and is it on the right?

• Yes – regular No – context-free• If not, can any of the rules reduce the length of a

string of terminals and non-terminals?• Yes – unrestricted No – context-sensitive

Grammar

Productions of the form:xA String of variables and terminals

),,,( PSTVG

Vocabulary Terminalsymbols

Startvariable

Non-Terminal

Definition: Context-Free Grammars

Derivation Tree of A Context-free Grammar

►Represents the language using an ordered rooted tree.

►Root represents the starting symbol.► Internal vertices represent the nonterminal symbol that

arise in the production.► Leaves represent the terminal symbols.

► If the production A → w arise in the derivation, where w is a word, the vertex that represents A has as children vertices that represent each symbol in w, in order from left to right.

Language Generated by a Grammar

• Example: Let G = ({S,A,a,b},{a,b}, S,{S → aA, S → b, A → aa}). What is L(G)?

• Easy: We can just draw a treeof all possible derivations.– We have: S aA aaa.– and S b.

• Answer: L = {aaa, b}.

S

aA b

aaaExample of aderivation treeor parse tree or sentence diagram.

Example: Derivation Tree

► Let G be a context-free grammar with the productions P = {S →aAB, A →Bba, B →bB, B →c}. The word w = acbabc can be derived from S as follows:

S ⇒ aAB →a(Bba)B ⇒ acbaB ⇒ acba(bB) ⇒ acbabcThus, the derivation tree is given as follows:

S

a A B

B b a

c

b B

c

Backus-Naur Form

• sentence noun phrase verb phrase• noun phrase article [adjective] noun• verb phrase verb [adverb]• article a | the• adjective large | hungry• noun rabbit | mathematician• verb eats | hops• adverb quickly | wildly

Square brackets []mean “optional”

Vertical barsmean “alternatives”

Generating Infinite Languages

• A simple PSG can easily generate an infinite language.

• Example: S → 11S, S → 0 (T = {0,1}).• The derivations are:– S 0– S 11S 110– S 11S 1111S 11110– and so on…

L = {(11)*0} – theset of all strings consisting of somenumber of concaten-ations of 11 with itself,followed by 0.

Another example

• Construct a PSG that generates the language L = {0n1n | nN}.– 0 and 1 here represent symbols being concatenated n

times, not integers being raised to the nth power.

• Solution strategy: Each step of the derivation should preserve the invariant that the number of 0’s = the number of 1’s in the template so far, and all 0’s come before all 1’s.

• Solution: S → 0S1, S → λ.

• Context-Sensitive Languages

• The language { anbncn | n 1} is context-sensitive but not context free.

• A grammar for this language is given by:• S aSBC | aBC• CB BC• aB ab• bB bb• bC bc• cC cc

Terminaland non-terminal

• A derivation from this grammar is:-• S aSBC• aaBCBC (using S aBC)• aabCBC (using aB ab)• aabBCC (using CB BC)• aabbCC (using bB bb)• aabbcC (using bC bc)• aabbcc (using cC cc)• which derives a2b2c2.